oj.uz

Submission #986447

# Submission time Handle Problem Language Result Execution time Memory
986447 2024-05-20T15:01:19 Z huutuan New Home (APIO18_new_home) C++14
80 / 100
 5000 ms 452960 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=1e6+10, inf=1e9;
vector<pair<pair<int, int>, pair<int, int>>> vq[N];
int ans[N];
vector<pair<int, int>> vpos;
vector<int> vtime;

struct SegmentTree1{
   int n;
   pair<int, int> t[N*2];
   void init(int _n){
      n=_n;
      for (int i=0; i<=n*2; ++i) t[i]={-inf, -inf};
   }
   void update(int pos, pair<int, int> val){
      --pos;
      for (t[pos+=n]=val; pos>1; pos>>=1) t[pos>>1].first=max(t[pos].first, t[pos^1].first), t[pos>>1].second=max(t[pos].second, t[pos^1].second);
   }
   int getl(int l, int r){
      --l;
      int res=-inf;
      for (l+=n, r+=n; l<r; l>>=1, r>>=1){
         if (l&1) res=max(res, t[l++].first);
         if (r&1) res=max(res, t[--r].first);
      }
      return res;
   }
   int getr(int l, int r){
      --l;
      int res=-inf;
      for (l+=n, r+=n; l<r; l>>=1, r>>=1){
         if (l&1) res=max(res, t[l++].second);
         if (r&1) res=max(res, t[--r].second);
      }
      return res;
   }
} st1;

struct SegmentTree2{
   int n;
   vector<pair<int, pair<int, int>>> t[N*4];
   void init(int _n){
      n=_n;
   }
   void update(int k, int l, int r, int L, int R, pair<int, pair<int, int>> val){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         t[k].push_back(val);
         return;
      }
      int mid=(l+r)>>1;
      update(k<<1, l, mid, L, R, val);
      update(k<<1|1, mid+1, r, L, R, val);
   }
   void dfs(int k, int l, int r){
      for (auto &i:t[k]){
         #ifdef sus
         cout << "update l " << i.first << ' ' << i.second.first << ' ' << i.second.second << endl;
         cout << "update r " << i.first << ' ' << i.second.first << ' ' << i.second.second << endl;
         #endif
         st1.update(i.first, {i.second.first+i.second.second, i.second.second-i.second.first});
      }
      if (l==r){
         for (auto &i:vq[l]){
            ans[i.second.first]=max(st1.getl(1, i.first.first)-i.second.second, st1.getr(i.first.second, st1.n)+i.second.second)/2;
         }
      }else{
         int mid=(l+r)>>1;
         dfs(k<<1, l, mid);
         dfs(k<<1|1, mid+1, r);
      }
      for (auto &i:t[k]){
         st1.update(i.first, {-inf, -inf});
      }
   }
} st2;

int n, q, k;
vector<pair<int, int>> v[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> k >> q;
   vtime.push_back(-inf*2); vpos.emplace_back(-inf*2, -1);
   vector<pair<int, pair<int, int>>> check;
   {
      map<pair<int, int>, vector<pair<int, int>>> mp;
      for (int i=1; i<=n; ++i){
         int x, t, l, r;
         cin >> x >> t >> l >> r; x*=2;
         mp[{x, t}].emplace_back(l, r);
      }
      for (auto &i:mp){
         sort(i.second.begin(), i.second.end());
         vector<pair<int, int>> vv;
         for (auto &j:i.second){
            if (vv.size() && vv.back().second+1>=j.first) vv.back().second=max(vv.back().second, j.second);
            else vv.push_back(j);
         }
         i.second.swap(vv);
      }
      for (auto &i:mp){
         int x=i.first.first, t=i.first.second;
         for (auto &j:i.second){
            int l=j.first, r=j.second;
            v[t].emplace_back(l, x);
            v[t].emplace_back(r+1, -x);
            check.push_back({l, {1, t}});
            check.push_back({r+1, {-1, t}});
         }
      }
   }
   vector<vector<int>> events;
   for (int i=1; i<=k; ++i){
      set<int> st;
      map<int, int> mp;
      sort(v[i].begin(), v[i].end());
      for (auto &j:v[i]){
         int pos=abs(j.second), t=j.first;
         auto it=st.lower_bound(pos);
         if (j.second>0){
            if (st.size()){
               int x=0, y=0;
               if (it==st.begin()) x=-*it, y=*it*2;
               else if (it==st.end()) x=inf+*prev(it), y=inf;
               else x=(*it+*prev(it))>>1, y=(*it-*prev(it))>>1; 
               events.push_back({mp[x], t-1, x, y});
               mp.erase(x);
            }
            {
               int x=0;
               if (it==st.begin()) x=-pos;
               else x=(pos+*prev(it))>>1;
               mp[x]=t;
            }
            {
               int x=0;
               if (it==st.end()) x=inf+pos;
               else x=(*it+pos)>>1;
               mp[x]=t;
            }
            st.emplace_hint(it, pos);
         }else{
            {
               int x=0, y=0;
               if (it==st.begin()) x=-pos, y=pos*2;
               else x=(pos+*prev(it))>>1, y=(pos-*prev(it))>>1;
               events.push_back({mp[x], t-1, x, y});
               mp.erase(x);
            }
            {
               int x=0, y=0;
               if (next(it)==st.end()) x=inf+pos, y=inf;
               else x=(*next(it)+pos)>>1, y=(*next(it)-pos)>>1;
               events.push_back({mp[x], t-1, x, y});
               mp.erase(x);
            }
            if ((int)st.size()>1){
               int x=0;
               if (it==st.begin()) x=-*next(it);
               else if (next(it)==st.end()) x=inf+*prev(it);
               else x=(*next(it)+*prev(it))>>1;
               mp[x]=t;
            }
            st.erase(it);
         }
      }
   }
   for (int i=0; i<(int)events.size(); ++i){
      vpos.emplace_back(events[i][2], i);
   }
   sort(vpos.begin(), vpos.end());
   vector<pair<int, int>> query(q);
   for (auto &i:query) cin >> i.first >> i.second, vtime.push_back(i.second), i.first*=2;
   sort(vtime.begin(), vtime.end()); vtime.resize(unique(vtime.begin(), vtime.end())-vtime.begin());
   for (int i=1; i<=q; ++i){
      int pl=lower_bound(vpos.begin(), vpos.end(), make_pair(query[i-1].first, -inf))-vpos.begin();
      int pr=lower_bound(vpos.begin(), vpos.end(), make_pair(query[i-1].first, inf))-vpos.begin()-1;
      vq[lower_bound(vtime.begin(), vtime.end(), query[i-1].second)-vtime.begin()].push_back({{pr, pl}, {i, query[i-1].first}});
      check.push_back({query[i-1].second, {2, i}});
   }
   st1.init((int)vpos.size()-1);
   st2.init((int)vtime.size()-1);
   for (int i=0; i<(int)events.size(); ++i){
      events[i][0]=lower_bound(vtime.begin(), vtime.end(), events[i][0])-vtime.begin();
      events[i][1]=upper_bound(vtime.begin(), vtime.end(), events[i][1])-vtime.begin()-1;
      st2.update(1, 1, st2.n, events[i][0], events[i][1], {lower_bound(vpos.begin(), vpos.end(), make_pair(events[i][2], i))-vpos.begin(), {events[i][2], events[i][3]}});
   }
   st2.dfs(1, 1, st2.n);
   sort(check.begin(), check.end());
   vector<int> cnt(k+1); int cnt0=k;
   for (auto &i:check){
      if (abs(i.second.first)==1){
         cnt0-=!cnt[i.second.second];
         cnt[i.second.second]+=i.second.first;
         cnt0+=!cnt[i.second.second];
      }else{
         if (cnt0) ans[i.second.second]=-1;
      }
   }
   for (int i=1; i<=q; ++i) cout << ans[i] << '\n';
   return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 156956 KB Output is correct
2 Correct 65 ms 157008 KB Output is correct
3 Correct 73 ms 158552 KB Output is correct
4 Correct 66 ms 158408 KB Output is correct
5 Correct 67 ms 158304 KB Output is correct
6 Correct 67 ms 158544 KB Output is correct
7 Correct 67 ms 158544 KB Output is correct
8 Correct 72 ms 158628 KB Output is correct
9 Correct 76 ms 158544 KB Output is correct
10 Correct 68 ms 158596 KB Output is correct
11 Correct 67 ms 158416 KB Output is correct
12 Correct 74 ms 158540 KB Output is correct
13 Correct 67 ms 158384 KB Output is correct
14 Correct 68 ms 158444 KB Output is correct
15 Correct 68 ms 158644 KB Output is correct
16 Correct 67 ms 158540 KB Output is correct
17 Correct 71 ms 158660 KB Output is correct
18 Correct 68 ms 158468 KB Output is correct
19 Correct 68 ms 158648 KB Output is correct
20 Correct 68 ms 158460 KB Output is correct
21 Correct 67 ms 158548 KB Output is correct
22 Correct 71 ms 158592 KB Output is correct
23 Correct 69 ms 158576 KB Output is correct
24 Correct 80 ms 158608 KB Output is correct
25 Correct 70 ms 158484 KB Output is correct
26 Correct 78 ms 158612 KB Output is correct
27 Correct 68 ms 158824 KB Output is correct
28 Correct 68 ms 158548 KB Output is correct
29 Correct 69 ms 158548 KB Output is correct
30 Correct 68 ms 158548 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 156956 KB Output is correct
2 Correct 65 ms 157008 KB Output is correct
3 Correct 73 ms 158552 KB Output is correct
4 Correct 66 ms 158408 KB Output is correct
5 Correct 67 ms 158304 KB Output is correct
6 Correct 67 ms 158544 KB Output is correct
7 Correct 67 ms 158544 KB Output is correct
8 Correct 72 ms 158628 KB Output is correct
9 Correct 76 ms 158544 KB Output is correct
10 Correct 68 ms 158596 KB Output is correct
11 Correct 67 ms 158416 KB Output is correct
12 Correct 74 ms 158540 KB Output is correct
13 Correct 67 ms 158384 KB Output is correct
14 Correct 68 ms 158444 KB Output is correct
15 Correct 68 ms 158644 KB Output is correct
16 Correct 67 ms 158540 KB Output is correct
17 Correct 71 ms 158660 KB Output is correct
18 Correct 68 ms 158468 KB Output is correct
19 Correct 68 ms 158648 KB Output is correct
20 Correct 68 ms 158460 KB Output is correct
21 Correct 67 ms 158548 KB Output is correct
22 Correct 71 ms 158592 KB Output is correct
23 Correct 69 ms 158576 KB Output is correct
24 Correct 80 ms 158608 KB Output is correct
25 Correct 70 ms 158484 KB Output is correct
26 Correct 78 ms 158612 KB Output is correct
27 Correct 68 ms 158824 KB Output is correct
28 Correct 68 ms 158548 KB Output is correct
29 Correct 69 ms 158548 KB Output is correct
30 Correct 68 ms 158548 KB Output is correct
31 Correct 678 ms 213996 KB Output is correct
32 Correct 108 ms 162364 KB Output is correct
33 Correct 647 ms 211704 KB Output is correct
34 Correct 625 ms 212464 KB Output is correct
35 Correct 690 ms 213440 KB Output is correct
36 Correct 690 ms 213524 KB Output is correct
37 Correct 559 ms 206236 KB Output is correct
38 Correct 527 ms 205800 KB Output is correct
39 Correct 423 ms 196320 KB Output is correct
40 Correct 439 ms 198548 KB Output is correct
41 Correct 502 ms 202600 KB Output is correct
42 Correct 510 ms 203496 KB Output is correct
43 Correct 104 ms 164224 KB Output is correct
44 Correct 529 ms 202124 KB Output is correct
45 Correct 459 ms 196616 KB Output is correct
46 Correct 365 ms 187780 KB Output is correct
47 Correct 298 ms 186096 KB Output is correct
48 Correct 281 ms 184560 KB Output is correct
49 Correct 343 ms 190604 KB Output is correct
50 Correct 466 ms 200204 KB Output is correct
51 Correct 316 ms 188076 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1435 ms 270376 KB Output is correct
2 Correct 1352 ms 269384 KB Output is correct
3 Correct 1248 ms 268524 KB Output is correct
4 Correct 1423 ms 268492 KB Output is correct
5 Correct 1399 ms 270440 KB Output is correct
6 Correct 1372 ms 269408 KB Output is correct
7 Correct 1215 ms 268236 KB Output is correct
8 Correct 1391 ms 268240 KB Output is correct
9 Correct 1435 ms 270180 KB Output is correct
10 Correct 1370 ms 268240 KB Output is correct
11 Correct 1033 ms 265600 KB Output is correct
12 Correct 1125 ms 270428 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3560 ms 375320 KB Output is correct
2 Correct 262 ms 177692 KB Output is correct
3 Correct 3800 ms 371276 KB Output is correct
4 Correct 2915 ms 333272 KB Output is correct
5 Correct 3804 ms 366932 KB Output is correct
6 Correct 3466 ms 361168 KB Output is correct
7 Correct 3882 ms 377880 KB Output is correct
8 Correct 3465 ms 374132 KB Output is correct
9 Correct 2479 ms 333596 KB Output is correct
10 Correct 3364 ms 362664 KB Output is correct
11 Correct 3250 ms 375056 KB Output is correct
12 Correct 3393 ms 375500 KB Output is correct
13 Correct 1731 ms 326068 KB Output is correct
14 Correct 1723 ms 322924 KB Output is correct
15 Correct 2003 ms 340416 KB Output is correct
16 Correct 2253 ms 354396 KB Output is correct
17 Correct 2163 ms 347528 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 156956 KB Output is correct
2 Correct 65 ms 157008 KB Output is correct
3 Correct 73 ms 158552 KB Output is correct
4 Correct 66 ms 158408 KB Output is correct
5 Correct 67 ms 158304 KB Output is correct
6 Correct 67 ms 158544 KB Output is correct
7 Correct 67 ms 158544 KB Output is correct
8 Correct 72 ms 158628 KB Output is correct
9 Correct 76 ms 158544 KB Output is correct
10 Correct 68 ms 158596 KB Output is correct
11 Correct 67 ms 158416 KB Output is correct
12 Correct 74 ms 158540 KB Output is correct
13 Correct 67 ms 158384 KB Output is correct
14 Correct 68 ms 158444 KB Output is correct
15 Correct 68 ms 158644 KB Output is correct
16 Correct 67 ms 158540 KB Output is correct
17 Correct 71 ms 158660 KB Output is correct
18 Correct 68 ms 158468 KB Output is correct
19 Correct 68 ms 158648 KB Output is correct
20 Correct 68 ms 158460 KB Output is correct
21 Correct 67 ms 158548 KB Output is correct
22 Correct 71 ms 158592 KB Output is correct
23 Correct 69 ms 158576 KB Output is correct
24 Correct 80 ms 158608 KB Output is correct
25 Correct 70 ms 158484 KB Output is correct
26 Correct 78 ms 158612 KB Output is correct
27 Correct 68 ms 158824 KB Output is correct
28 Correct 68 ms 158548 KB Output is correct
29 Correct 69 ms 158548 KB Output is correct
30 Correct 68 ms 158548 KB Output is correct
31 Correct 678 ms 213996 KB Output is correct
32 Correct 108 ms 162364 KB Output is correct
33 Correct 647 ms 211704 KB Output is correct
34 Correct 625 ms 212464 KB Output is correct
35 Correct 690 ms 213440 KB Output is correct
36 Correct 690 ms 213524 KB Output is correct
37 Correct 559 ms 206236 KB Output is correct
38 Correct 527 ms 205800 KB Output is correct
39 Correct 423 ms 196320 KB Output is correct
40 Correct 439 ms 198548 KB Output is correct
41 Correct 502 ms 202600 KB Output is correct
42 Correct 510 ms 203496 KB Output is correct
43 Correct 104 ms 164224 KB Output is correct
44 Correct 529 ms 202124 KB Output is correct
45 Correct 459 ms 196616 KB Output is correct
46 Correct 365 ms 187780 KB Output is correct
47 Correct 298 ms 186096 KB Output is correct
48 Correct 281 ms 184560 KB Output is correct
49 Correct 343 ms 190604 KB Output is correct
50 Correct 466 ms 200204 KB Output is correct
51 Correct 316 ms 188076 KB Output is correct
52 Correct 521 ms 202624 KB Output is correct
53 Correct 525 ms 200496 KB Output is correct
54 Correct 686 ms 210924 KB Output is correct
55 Correct 537 ms 207984 KB Output is correct
56 Correct 578 ms 208504 KB Output is correct
57 Correct 540 ms 204388 KB Output is correct
58 Correct 542 ms 205052 KB Output is correct
59 Correct 565 ms 205996 KB Output is correct
60 Correct 562 ms 203980 KB Output is correct
61 Correct 175 ms 178616 KB Output is correct
62 Correct 510 ms 205880 KB Output is correct
63 Correct 622 ms 210052 KB Output is correct
64 Correct 656 ms 211932 KB Output is correct
65 Correct 643 ms 212500 KB Output is correct
66 Correct 571 ms 206452 KB Output is correct
67 Correct 279 ms 181916 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 156956 KB Output is correct
2 Correct 65 ms 157008 KB Output is correct
3 Correct 73 ms 158552 KB Output is correct
4 Correct 66 ms 158408 KB Output is correct
5 Correct 67 ms 158304 KB Output is correct
6 Correct 67 ms 158544 KB Output is correct
7 Correct 67 ms 158544 KB Output is correct
8 Correct 72 ms 158628 KB Output is correct
9 Correct 76 ms 158544 KB Output is correct
10 Correct 68 ms 158596 KB Output is correct
11 Correct 67 ms 158416 KB Output is correct
12 Correct 74 ms 158540 KB Output is correct
13 Correct 67 ms 158384 KB Output is correct
14 Correct 68 ms 158444 KB Output is correct
15 Correct 68 ms 158644 KB Output is correct
16 Correct 67 ms 158540 KB Output is correct
17 Correct 71 ms 158660 KB Output is correct
18 Correct 68 ms 158468 KB Output is correct
19 Correct 68 ms 158648 KB Output is correct
20 Correct 68 ms 158460 KB Output is correct
21 Correct 67 ms 158548 KB Output is correct
22 Correct 71 ms 158592 KB Output is correct
23 Correct 69 ms 158576 KB Output is correct
24 Correct 80 ms 158608 KB Output is correct
25 Correct 70 ms 158484 KB Output is correct
26 Correct 78 ms 158612 KB Output is correct
27 Correct 68 ms 158824 KB Output is correct
28 Correct 68 ms 158548 KB Output is correct
29 Correct 69 ms 158548 KB Output is correct
30 Correct 68 ms 158548 KB Output is correct
31 Correct 678 ms 213996 KB Output is correct
32 Correct 108 ms 162364 KB Output is correct
33 Correct 647 ms 211704 KB Output is correct
34 Correct 625 ms 212464 KB Output is correct
35 Correct 690 ms 213440 KB Output is correct
36 Correct 690 ms 213524 KB Output is correct
37 Correct 559 ms 206236 KB Output is correct
38 Correct 527 ms 205800 KB Output is correct
39 Correct 423 ms 196320 KB Output is correct
40 Correct 439 ms 198548 KB Output is correct
41 Correct 502 ms 202600 KB Output is correct
42 Correct 510 ms 203496 KB Output is correct
43 Correct 104 ms 164224 KB Output is correct
44 Correct 529 ms 202124 KB Output is correct
45 Correct 459 ms 196616 KB Output is correct
46 Correct 365 ms 187780 KB Output is correct
47 Correct 298 ms 186096 KB Output is correct
48 Correct 281 ms 184560 KB Output is correct
49 Correct 343 ms 190604 KB Output is correct
50 Correct 466 ms 200204 KB Output is correct
51 Correct 316 ms 188076 KB Output is correct
52 Correct 1435 ms 270376 KB Output is correct
53 Correct 1352 ms 269384 KB Output is correct
54 Correct 1248 ms 268524 KB Output is correct
55 Correct 1423 ms 268492 KB Output is correct
56 Correct 1399 ms 270440 KB Output is correct
57 Correct 1372 ms 269408 KB Output is correct
58 Correct 1215 ms 268236 KB Output is correct
59 Correct 1391 ms 268240 KB Output is correct
60 Correct 1435 ms 270180 KB Output is correct
61 Correct 1370 ms 268240 KB Output is correct
62 Correct 1033 ms 265600 KB Output is correct
63 Correct 1125 ms 270428 KB Output is correct
64 Correct 3560 ms 375320 KB Output is correct
65 Correct 262 ms 177692 KB Output is correct
66 Correct 3800 ms 371276 KB Output is correct
67 Correct 2915 ms 333272 KB Output is correct
68 Correct 3804 ms 366932 KB Output is correct
69 Correct 3466 ms 361168 KB Output is correct
70 Correct 3882 ms 377880 KB Output is correct
71 Correct 3465 ms 374132 KB Output is correct
72 Correct 2479 ms 333596 KB Output is correct
73 Correct 3364 ms 362664 KB Output is correct
74 Correct 3250 ms 375056 KB Output is correct
75 Correct 3393 ms 375500 KB Output is correct
76 Correct 1731 ms 326068 KB Output is correct
77 Correct 1723 ms 322924 KB Output is correct
78 Correct 2003 ms 340416 KB Output is correct
79 Correct 2253 ms 354396 KB Output is correct
80 Correct 2163 ms 347528 KB Output is correct
81 Correct 521 ms 202624 KB Output is correct
82 Correct 525 ms 200496 KB Output is correct
83 Correct 686 ms 210924 KB Output is correct
84 Correct 537 ms 207984 KB Output is correct
85 Correct 578 ms 208504 KB Output is correct
86 Correct 540 ms 204388 KB Output is correct
87 Correct 542 ms 205052 KB Output is correct
88 Correct 565 ms 205996 KB Output is correct
89 Correct 562 ms 203980 KB Output is correct
90 Correct 175 ms 178616 KB Output is correct
91 Correct 510 ms 205880 KB Output is correct
92 Correct 622 ms 210052 KB Output is correct
93 Correct 656 ms 211932 KB Output is correct
94 Correct 643 ms 212500 KB Output is correct
95 Correct 571 ms 206452 KB Output is correct
96 Correct 279 ms 181916 KB Output is correct
97 Correct 3621 ms 419056 KB Output is correct
98 Correct 274 ms 179760 KB Output is correct
99 Execution timed out 5007 ms 452960 KB Time limit exceeded
100 Halted 0 ms 0 KB -