fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. #define maxN 100007
  8. #define oo 1000000000000000000
  9.  
  10. long long ans[maxN];
  11. int n;
  12.  
  13. struct planet
  14. {
  15.     int t;
  16.     int ll, lr, rl, rr;
  17. };
  18. planet inp[maxN];
  19.  
  20. struct event
  21. {
  22.     int id;
  23.     bool sta;
  24.     int t;
  25. };
  26.  
  27. event line[maxN*2];
  28.  
  29. bool cmp(event x, event y)
  30. {
  31.     if(x.t != y.t)
  32.         return x.t < y.t;
  33.     return x.sta > y.sta;
  34. }
  35.  
  36. long long st[maxN*4];
  37.  
  38. void readData()
  39. {
  40.     cin >> n;
  41.     for(int i = 1; i <= n; i++)
  42.     {
  43.         cin >> inp[i].t >> inp[i].ll >> inp[i].lr >> inp[i].rl >> inp[i].rr;
  44.         line[i].id = i;
  45.         line[i].t = inp[i].rl;
  46.         line[i].sta = true;
  47.         line[i+n].id = i;
  48.         line[i+n].t = inp[i].rr;
  49.         line[i+n].sta = false;
  50.     }
  51.     sort(line+1, line+2*n+1, cmp);
  52.     for(int i = 0; i < 4*maxN; i++)
  53.         st[i] = oo;
  54. }
  55.  
  56. void update(int id, int l, int r, int pos, long long val)
  57. {
  58.     if(l == r)
  59.     {
  60.         st[id] = val;
  61.         return;
  62.     }
  63.     int mid = (l+r)/2;
  64.     if(pos <= mid)
  65.         update(id*2, l, mid, pos, val);
  66.     else update(id*2+1, mid+1, r, pos, val);
  67.     st[id] = min(st[id*2], st[id*2+1]);
  68. }
  69.  
  70. long long query(int id, int l, int r, int u, int v)
  71. {
  72.     if(l > v || u > r)
  73.         return oo;
  74.     if(u <= l && r <= v)
  75.         return st[id];
  76.     int mid = (l+r)/2;
  77.     long long ans1 = query(id*2, l, mid, u, v);
  78.     long long ans2 = query(id*2+1, mid+1, r, u, v);
  79.     return min(ans1, ans2);
  80. }
  81.  
  82. void solve()
  83. {
  84.     int i = 0;
  85.     queue<int>add;
  86.     for(int curTime = 1; curTime <= n; curTime++)
  87.     {
  88.         while(i < 2*n && line[i+1].t == curTime && line[i+1].sta)
  89.         {
  90.             ++i;
  91.             if (line[i].id < curTime)
  92.                 update(1, 1, n, line[i].id, ans[line[i].id] + inp[line[i].id].t - line[i].id);
  93.             else add.push(i);
  94.         }
  95.         if(curTime == 1)
  96.             ans[curTime] = 0;
  97.         else
  98.         {
  99.             long long curAns = query(1, 1, n, inp[curTime].ll, inp[curTime].lr);
  100.             if(curAns == oo)
  101.             {
  102.                 ans[curTime] = oo;
  103.             }
  104.             else ans[curTime] = curAns + inp[curTime].t + curTime;
  105.         }
  106.         while(!add.empty())
  107.         {
  108.             int j = add.front();
  109.             add.pop();
  110.             update(1, 1, n, line[j].id, ans[line[j].id] + inp[line[j].id].t - line[j].id);
  111.         }
  112.         while(i < 2*n && line[i+1].t == curTime && !line[i+1].sta)
  113.         {
  114.             i++;
  115.             update(1, 1, n, line[i].id, oo);
  116.         }
  117.     }
  118.     for(int i = 2; i <= n; i++)
  119.         if(ans[i] < oo)
  120.             cout << ans[i] << " ";
  121.         else cout << "-1 ";
  122. }
  123.  
  124. int main()
  125. {
  126.     ios_base::sync_with_stdio(0);
  127.     cin.tie(0);
  128.     readData();
  129.     solve();
  130.     return 0;
  131. }
  132.  
Success #stdin #stdout 0.01s 10348KB
comments (?)
stdin
copy 
5
2 1 1 2 4
7 1 1 5 5
1 1 2 4 5
0 2 3 4 5
3 1 4 5 5
stdout
copy 
10 5 7 11
https://ideone.com/ytEryu
language:
C++14 (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!