oj.uz

Submission #986475

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

using namespace std;

const int N=1e6+10, inf=1e9;

long long stk[N*64];
int stk_size;

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;
      pos+=n;
      stk[++stk_size]=(((long long)pos)<<32)|(t[pos].first&((1ll<<32)-1));
      stk[++stk_size]=(((long long)pos)<<32)|(t[pos].second&((1ll<<32)-1));
      t[pos]=val;
      for (; pos>1; pos>>=1){
         stk[++stk_size]=(((long long)(pos>>1))<<32)|(t[pos>>1].first&((1ll<<32)-1));
         stk[++stk_size]=(((long long)(pos>>1))<<32)|(t[pos>>1].second&((1ll<<32)-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){
      int size=stk_size;
      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);
      }
      while (stk_size!=size){
         st1.t[stk[stk_size]>>32].second=(int)(stk[stk_size]&((1ll<<32)-1));
         --stk_size;
         st1.t[stk[stk_size]>>32].first=(int)(stk[stk_size]&((1ll<<32)-1));
         --stk_size;
      }
   }
} 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;
      if (events[i][0]<=events[i][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 69 ms 160592 KB Output is correct
2 Correct 63 ms 160592 KB Output is correct
3 Correct 64 ms 160596 KB Output is correct
4 Correct 64 ms 160476 KB Output is correct
5 Correct 65 ms 160648 KB Output is correct
6 Correct 66 ms 160948 KB Output is correct
7 Correct 66 ms 160776 KB Output is correct
8 Correct 67 ms 160708 KB Output is correct
9 Correct 64 ms 160852 KB Output is correct
10 Correct 65 ms 160848 KB Output is correct
11 Correct 68 ms 160836 KB Output is correct
12 Correct 64 ms 160848 KB Output is correct
13 Correct 62 ms 160592 KB Output is correct
14 Correct 64 ms 160708 KB Output is correct
15 Correct 64 ms 160780 KB Output is correct
16 Correct 65 ms 160848 KB Output is correct
17 Correct 64 ms 160900 KB Output is correct
18 Correct 64 ms 160904 KB Output is correct
19 Correct 67 ms 160852 KB Output is correct
20 Correct 66 ms 160744 KB Output is correct
21 Correct 63 ms 160592 KB Output is correct
22 Correct 64 ms 160848 KB Output is correct
23 Correct 63 ms 160872 KB Output is correct
24 Correct 64 ms 160848 KB Output is correct
25 Correct 67 ms 160852 KB Output is correct
26 Correct 69 ms 160728 KB Output is correct
27 Correct 65 ms 160596 KB Output is correct
28 Correct 68 ms 160720 KB Output is correct
29 Correct 64 ms 160604 KB Output is correct
30 Correct 64 ms 160784 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 160592 KB Output is correct
2 Correct 63 ms 160592 KB Output is correct
3 Correct 64 ms 160596 KB Output is correct
4 Correct 64 ms 160476 KB Output is correct
5 Correct 65 ms 160648 KB Output is correct
6 Correct 66 ms 160948 KB Output is correct
7 Correct 66 ms 160776 KB Output is correct
8 Correct 67 ms 160708 KB Output is correct
9 Correct 64 ms 160852 KB Output is correct
10 Correct 65 ms 160848 KB Output is correct
11 Correct 68 ms 160836 KB Output is correct
12 Correct 64 ms 160848 KB Output is correct
13 Correct 62 ms 160592 KB Output is correct
14 Correct 64 ms 160708 KB Output is correct
15 Correct 64 ms 160780 KB Output is correct
16 Correct 65 ms 160848 KB Output is correct
17 Correct 64 ms 160900 KB Output is correct
18 Correct 64 ms 160904 KB Output is correct
19 Correct 67 ms 160852 KB Output is correct
20 Correct 66 ms 160744 KB Output is correct
21 Correct 63 ms 160592 KB Output is correct
22 Correct 64 ms 160848 KB Output is correct
23 Correct 63 ms 160872 KB Output is correct
24 Correct 64 ms 160848 KB Output is correct
25 Correct 67 ms 160852 KB Output is correct
26 Correct 69 ms 160728 KB Output is correct
27 Correct 65 ms 160596 KB Output is correct
28 Correct 68 ms 160720 KB Output is correct
29 Correct 64 ms 160604 KB Output is correct
30 Correct 64 ms 160784 KB Output is correct
31 Correct 656 ms 231916 KB Output is correct
32 Correct 101 ms 164360 KB Output is correct
33 Correct 646 ms 218732 KB Output is correct
34 Correct 618 ms 219368 KB Output is correct
35 Correct 685 ms 231044 KB Output is correct
36 Correct 672 ms 231280 KB Output is correct
37 Correct 508 ms 208280 KB Output is correct
38 Correct 530 ms 207972 KB Output is correct
39 Correct 402 ms 198452 KB Output is correct
40 Correct 415 ms 200732 KB Output is correct
41 Correct 489 ms 204616 KB Output is correct
42 Correct 486 ms 205548 KB Output is correct
43 Correct 104 ms 166224 KB Output is correct
44 Correct 468 ms 204128 KB Output is correct
45 Correct 457 ms 198628 KB Output is correct
46 Correct 344 ms 189932 KB Output is correct
47 Correct 271 ms 187996 KB Output is correct
48 Correct 254 ms 186332 KB Output is correct
49 Correct 319 ms 192552 KB Output is correct
50 Correct 402 ms 202236 KB Output is correct
51 Correct 307 ms 190196 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1382 ms 385508 KB Output is correct
2 Correct 1291 ms 365596 KB Output is correct
3 Correct 1340 ms 458760 KB Output is correct
4 Correct 1344 ms 396144 KB Output is correct
5 Correct 1372 ms 366384 KB Output is correct
6 Correct 1354 ms 365908 KB Output is correct
7 Correct 1331 ms 458616 KB Output is correct
8 Correct 1448 ms 395724 KB Output is correct
9 Correct 1327 ms 377012 KB Output is correct
10 Correct 1332 ms 367776 KB Output is correct
11 Correct 970 ms 361484 KB Output is correct
12 Correct 1004 ms 365776 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3073 ms 474644 KB Output is correct
2 Correct 245 ms 180108 KB Output is correct
3 Correct 3125 ms 471156 KB Output is correct
4 Correct 2476 ms 526580 KB Output is correct
5 Correct 3059 ms 484988 KB Output is correct
6 Correct 3076 ms 491528 KB Output is correct
7 Correct 3558 ms 476856 KB Output is correct
8 Correct 3171 ms 471720 KB Output is correct
9 Correct 2465 ms 523868 KB Output is correct
10 Correct 3114 ms 483848 KB Output is correct
11 Correct 3134 ms 477276 KB Output is correct
12 Correct 3116 ms 472792 KB Output is correct
13 Correct 1637 ms 420020 KB Output is correct
14 Correct 1651 ms 415020 KB Output is correct
15 Correct 1894 ms 435220 KB Output is correct
16 Correct 2144 ms 451160 KB Output is correct
17 Correct 2037 ms 441908 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 160592 KB Output is correct
2 Correct 63 ms 160592 KB Output is correct
3 Correct 64 ms 160596 KB Output is correct
4 Correct 64 ms 160476 KB Output is correct
5 Correct 65 ms 160648 KB Output is correct
6 Correct 66 ms 160948 KB Output is correct
7 Correct 66 ms 160776 KB Output is correct
8 Correct 67 ms 160708 KB Output is correct
9 Correct 64 ms 160852 KB Output is correct
10 Correct 65 ms 160848 KB Output is correct
11 Correct 68 ms 160836 KB Output is correct
12 Correct 64 ms 160848 KB Output is correct
13 Correct 62 ms 160592 KB Output is correct
14 Correct 64 ms 160708 KB Output is correct
15 Correct 64 ms 160780 KB Output is correct
16 Correct 65 ms 160848 KB Output is correct
17 Correct 64 ms 160900 KB Output is correct
18 Correct 64 ms 160904 KB Output is correct
19 Correct 67 ms 160852 KB Output is correct
20 Correct 66 ms 160744 KB Output is correct
21 Correct 63 ms 160592 KB Output is correct
22 Correct 64 ms 160848 KB Output is correct
23 Correct 63 ms 160872 KB Output is correct
24 Correct 64 ms 160848 KB Output is correct
25 Correct 67 ms 160852 KB Output is correct
26 Correct 69 ms 160728 KB Output is correct
27 Correct 65 ms 160596 KB Output is correct
28 Correct 68 ms 160720 KB Output is correct
29 Correct 64 ms 160604 KB Output is correct
30 Correct 64 ms 160784 KB Output is correct
31 Correct 656 ms 231916 KB Output is correct
32 Correct 101 ms 164360 KB Output is correct
33 Correct 646 ms 218732 KB Output is correct
34 Correct 618 ms 219368 KB Output is correct
35 Correct 685 ms 231044 KB Output is correct
36 Correct 672 ms 231280 KB Output is correct
37 Correct 508 ms 208280 KB Output is correct
38 Correct 530 ms 207972 KB Output is correct
39 Correct 402 ms 198452 KB Output is correct
40 Correct 415 ms 200732 KB Output is correct
41 Correct 489 ms 204616 KB Output is correct
42 Correct 486 ms 205548 KB Output is correct
43 Correct 104 ms 166224 KB Output is correct
44 Correct 468 ms 204128 KB Output is correct
45 Correct 457 ms 198628 KB Output is correct
46 Correct 344 ms 189932 KB Output is correct
47 Correct 271 ms 187996 KB Output is correct
48 Correct 254 ms 186332 KB Output is correct
49 Correct 319 ms 192552 KB Output is correct
50 Correct 402 ms 202236 KB Output is correct
51 Correct 307 ms 190196 KB Output is correct
52 Correct 494 ms 236392 KB Output is correct
53 Correct 458 ms 213192 KB Output is correct
54 Correct 613 ms 234504 KB Output is correct
55 Correct 510 ms 219884 KB Output is correct
56 Correct 520 ms 226288 KB Output is correct
57 Correct 488 ms 208020 KB Output is correct
58 Correct 518 ms 217168 KB Output is correct
59 Correct 509 ms 223956 KB Output is correct
60 Correct 499 ms 207980 KB Output is correct
61 Correct 175 ms 212480 KB Output is correct
62 Correct 484 ms 239880 KB Output is correct
63 Correct 574 ms 233140 KB Output is correct
64 Correct 619 ms 229392 KB Output is correct
65 Correct 584 ms 218608 KB Output is correct
66 Correct 533 ms 208636 KB Output is correct
67 Correct 281 ms 187720 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 160592 KB Output is correct
2 Correct 63 ms 160592 KB Output is correct
3 Correct 64 ms 160596 KB Output is correct
4 Correct 64 ms 160476 KB Output is correct
5 Correct 65 ms 160648 KB Output is correct
6 Correct 66 ms 160948 KB Output is correct
7 Correct 66 ms 160776 KB Output is correct
8 Correct 67 ms 160708 KB Output is correct
9 Correct 64 ms 160852 KB Output is correct
10 Correct 65 ms 160848 KB Output is correct
11 Correct 68 ms 160836 KB Output is correct
12 Correct 64 ms 160848 KB Output is correct
13 Correct 62 ms 160592 KB Output is correct
14 Correct 64 ms 160708 KB Output is correct
15 Correct 64 ms 160780 KB Output is correct
16 Correct 65 ms 160848 KB Output is correct
17 Correct 64 ms 160900 KB Output is correct
18 Correct 64 ms 160904 KB Output is correct
19 Correct 67 ms 160852 KB Output is correct
20 Correct 66 ms 160744 KB Output is correct
21 Correct 63 ms 160592 KB Output is correct
22 Correct 64 ms 160848 KB Output is correct
23 Correct 63 ms 160872 KB Output is correct
24 Correct 64 ms 160848 KB Output is correct
25 Correct 67 ms 160852 KB Output is correct
26 Correct 69 ms 160728 KB Output is correct
27 Correct 65 ms 160596 KB Output is correct
28 Correct 68 ms 160720 KB Output is correct
29 Correct 64 ms 160604 KB Output is correct
30 Correct 64 ms 160784 KB Output is correct
31 Correct 656 ms 231916 KB Output is correct
32 Correct 101 ms 164360 KB Output is correct
33 Correct 646 ms 218732 KB Output is correct
34 Correct 618 ms 219368 KB Output is correct
35 Correct 685 ms 231044 KB Output is correct
36 Correct 672 ms 231280 KB Output is correct
37 Correct 508 ms 208280 KB Output is correct
38 Correct 530 ms 207972 KB Output is correct
39 Correct 402 ms 198452 KB Output is correct
40 Correct 415 ms 200732 KB Output is correct
41 Correct 489 ms 204616 KB Output is correct
42 Correct 486 ms 205548 KB Output is correct
43 Correct 104 ms 166224 KB Output is correct
44 Correct 468 ms 204128 KB Output is correct
45 Correct 457 ms 198628 KB Output is correct
46 Correct 344 ms 189932 KB Output is correct
47 Correct 271 ms 187996 KB Output is correct
48 Correct 254 ms 186332 KB Output is correct
49 Correct 319 ms 192552 KB Output is correct
50 Correct 402 ms 202236 KB Output is correct
51 Correct 307 ms 190196 KB Output is correct
52 Correct 1382 ms 385508 KB Output is correct
53 Correct 1291 ms 365596 KB Output is correct
54 Correct 1340 ms 458760 KB Output is correct
55 Correct 1344 ms 396144 KB Output is correct
56 Correct 1372 ms 366384 KB Output is correct
57 Correct 1354 ms 365908 KB Output is correct
58 Correct 1331 ms 458616 KB Output is correct
59 Correct 1448 ms 395724 KB Output is correct
60 Correct 1327 ms 377012 KB Output is correct
61 Correct 1332 ms 367776 KB Output is correct
62 Correct 970 ms 361484 KB Output is correct
63 Correct 1004 ms 365776 KB Output is correct
64 Correct 3073 ms 474644 KB Output is correct
65 Correct 245 ms 180108 KB Output is correct
66 Correct 3125 ms 471156 KB Output is correct
67 Correct 2476 ms 526580 KB Output is correct
68 Correct 3059 ms 484988 KB Output is correct
69 Correct 3076 ms 491528 KB Output is correct
70 Correct 3558 ms 476856 KB Output is correct
71 Correct 3171 ms 471720 KB Output is correct
72 Correct 2465 ms 523868 KB Output is correct
73 Correct 3114 ms 483848 KB Output is correct
74 Correct 3134 ms 477276 KB Output is correct
75 Correct 3116 ms 472792 KB Output is correct
76 Correct 1637 ms 420020 KB Output is correct
77 Correct 1651 ms 415020 KB Output is correct
78 Correct 1894 ms 435220 KB Output is correct
79 Correct 2144 ms 451160 KB Output is correct
80 Correct 2037 ms 441908 KB Output is correct
81 Correct 494 ms 236392 KB Output is correct
82 Correct 458 ms 213192 KB Output is correct
83 Correct 613 ms 234504 KB Output is correct
84 Correct 510 ms 219884 KB Output is correct
85 Correct 520 ms 226288 KB Output is correct
86 Correct 488 ms 208020 KB Output is correct
87 Correct 518 ms 217168 KB Output is correct
88 Correct 509 ms 223956 KB Output is correct
89 Correct 499 ms 207980 KB Output is correct
90 Correct 175 ms 212480 KB Output is correct
91 Correct 484 ms 239880 KB Output is correct
92 Correct 574 ms 233140 KB Output is correct
93 Correct 619 ms 229392 KB Output is correct
94 Correct 584 ms 218608 KB Output is correct
95 Correct 533 ms 208636 KB Output is correct
96 Correct 281 ms 187720 KB Output is correct
97 Correct 3635 ms 609352 KB Output is correct
98 Correct 264 ms 182004 KB Output is correct
99 Correct 4567 ms 488804 KB Output is correct
100 Correct 3361 ms 465056 KB Output is correct
101 Correct 4569 ms 589484 KB Output is correct
102 Execution timed out 5067 ms 572680 KB Time limit exceeded
103 Halted 0 ms 0 KB -