oj.uz

Submission #986441

# Submission time Handle Problem Language Result Execution time Memory
986441 2024-05-20T14:42:49 Z huutuan New Home (APIO18_new_home) C++14
57 / 100
 5000 ms 416988 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;
   vector<int> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, -inf);
   }
   void update(int k, int l, int r, int pos, int val){
      if (r<pos || pos<l) return;
      if (l==r){
         t[k]=val;
         return;
      }
      int mid=(l+r)>>1;
      update(k<<1, l, mid, pos, val);
      update(k<<1|1, mid+1, r, pos, val);
      t[k]=max(t[k<<1], t[k<<1|1]);
   }
   int get(int k, int l, int r, int L, int R){
      if (r<L || R<l) return -inf;
      if (L<=l && r<=R) return t[k];
      int mid=(l+r)>>1;
      return max(get(k<<1, l, mid, L, R), get(k<<1|1, mid+1, r, L, R));
   }
} stl, str;

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
         stl.update(1, 1, stl.n, i.first, i.second.first+i.second.second);
         str.update(1, 1, str.n, i.first, i.second.second-i.second.first);
      }
      if (l==r){
         for (auto &i:vq[l]){
            if (i.second.first==4){
               i.second.first=4;
            }
            ans[i.second.first]=max(stl.get(1, 1, stl.n, 1, i.first.first)-i.second.second, str.get(1, 1, str.n, i.first.second, str.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]){
         stl.update(1, 1, stl.n, i.first, -inf);
         str.update(1, 1, str.n, i.first, -inf);
      }
   }
} st;

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}});
   }
   stl.init((int)vpos.size()-1);
   str.init((int)vpos.size()-1);
   st.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;
      st.update(1, 1, st.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]}});
   }
   st.dfs(1, 1, st.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 65 ms 141464 KB Output is correct
2 Correct 60 ms 141396 KB Output is correct
3 Correct 64 ms 141392 KB Output is correct
4 Correct 66 ms 141392 KB Output is correct
5 Correct 65 ms 141560 KB Output is correct
6 Correct 65 ms 141648 KB Output is correct
7 Correct 65 ms 141648 KB Output is correct
8 Correct 66 ms 141680 KB Output is correct
9 Correct 64 ms 141660 KB Output is correct
10 Correct 67 ms 141652 KB Output is correct
11 Correct 64 ms 141616 KB Output is correct
12 Correct 64 ms 141648 KB Output is correct
13 Correct 64 ms 141684 KB Output is correct
14 Correct 63 ms 141704 KB Output is correct
15 Correct 64 ms 141744 KB Output is correct
16 Correct 64 ms 141648 KB Output is correct
17 Correct 67 ms 141648 KB Output is correct
18 Correct 64 ms 141652 KB Output is correct
19 Correct 65 ms 141776 KB Output is correct
20 Correct 68 ms 141652 KB Output is correct
21 Correct 62 ms 141648 KB Output is correct
22 Correct 63 ms 141772 KB Output is correct
23 Correct 66 ms 141648 KB Output is correct
24 Correct 65 ms 141648 KB Output is correct
25 Correct 64 ms 141648 KB Output is correct
26 Correct 65 ms 141652 KB Output is correct
27 Correct 66 ms 141652 KB Output is correct
28 Correct 64 ms 141652 KB Output is correct
29 Correct 66 ms 141724 KB Output is correct
30 Correct 64 ms 141648 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 141464 KB Output is correct
2 Correct 60 ms 141396 KB Output is correct
3 Correct 64 ms 141392 KB Output is correct
4 Correct 66 ms 141392 KB Output is correct
5 Correct 65 ms 141560 KB Output is correct
6 Correct 65 ms 141648 KB Output is correct
7 Correct 65 ms 141648 KB Output is correct
8 Correct 66 ms 141680 KB Output is correct
9 Correct 64 ms 141660 KB Output is correct
10 Correct 67 ms 141652 KB Output is correct
11 Correct 64 ms 141616 KB Output is correct
12 Correct 64 ms 141648 KB Output is correct
13 Correct 64 ms 141684 KB Output is correct
14 Correct 63 ms 141704 KB Output is correct
15 Correct 64 ms 141744 KB Output is correct
16 Correct 64 ms 141648 KB Output is correct
17 Correct 67 ms 141648 KB Output is correct
18 Correct 64 ms 141652 KB Output is correct
19 Correct 65 ms 141776 KB Output is correct
20 Correct 68 ms 141652 KB Output is correct
21 Correct 62 ms 141648 KB Output is correct
22 Correct 63 ms 141772 KB Output is correct
23 Correct 66 ms 141648 KB Output is correct
24 Correct 65 ms 141648 KB Output is correct
25 Correct 64 ms 141648 KB Output is correct
26 Correct 65 ms 141652 KB Output is correct
27 Correct 66 ms 141652 KB Output is correct
28 Correct 64 ms 141652 KB Output is correct
29 Correct 66 ms 141724 KB Output is correct
30 Correct 64 ms 141648 KB Output is correct
31 Correct 1478 ms 209344 KB Output is correct
32 Correct 102 ms 145488 KB Output is correct
33 Correct 1348 ms 207420 KB Output is correct
34 Correct 1363 ms 207840 KB Output is correct
35 Correct 1455 ms 208700 KB Output is correct
36 Correct 1483 ms 209768 KB Output is correct
37 Correct 1062 ms 201704 KB Output is correct
38 Correct 1028 ms 201332 KB Output is correct
39 Correct 683 ms 191728 KB Output is correct
40 Correct 769 ms 193900 KB Output is correct
41 Correct 952 ms 197968 KB Output is correct
42 Correct 972 ms 198632 KB Output is correct
43 Correct 97 ms 147244 KB Output is correct
44 Correct 915 ms 197384 KB Output is correct
45 Correct 759 ms 191728 KB Output is correct
46 Correct 524 ms 183100 KB Output is correct
47 Correct 400 ms 180460 KB Output is correct
48 Correct 361 ms 178672 KB Output is correct
49 Correct 569 ms 185460 KB Output is correct
50 Correct 770 ms 195276 KB Output is correct
51 Correct 500 ms 182932 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1616 ms 312672 KB Output is correct
2 Correct 1531 ms 313800 KB Output is correct
3 Correct 1534 ms 301436 KB Output is correct
4 Correct 1631 ms 309592 KB Output is correct
5 Correct 1563 ms 314396 KB Output is correct
6 Correct 1513 ms 313212 KB Output is correct
7 Correct 1546 ms 301456 KB Output is correct
8 Correct 1721 ms 309076 KB Output is correct
9 Correct 1672 ms 314168 KB Output is correct
10 Correct 1670 ms 316056 KB Output is correct
11 Correct 1166 ms 310704 KB Output is correct
12 Correct 1210 ms 314552 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5042 ms 416988 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 141464 KB Output is correct
2 Correct 60 ms 141396 KB Output is correct
3 Correct 64 ms 141392 KB Output is correct
4 Correct 66 ms 141392 KB Output is correct
5 Correct 65 ms 141560 KB Output is correct
6 Correct 65 ms 141648 KB Output is correct
7 Correct 65 ms 141648 KB Output is correct
8 Correct 66 ms 141680 KB Output is correct
9 Correct 64 ms 141660 KB Output is correct
10 Correct 67 ms 141652 KB Output is correct
11 Correct 64 ms 141616 KB Output is correct
12 Correct 64 ms 141648 KB Output is correct
13 Correct 64 ms 141684 KB Output is correct
14 Correct 63 ms 141704 KB Output is correct
15 Correct 64 ms 141744 KB Output is correct
16 Correct 64 ms 141648 KB Output is correct
17 Correct 67 ms 141648 KB Output is correct
18 Correct 64 ms 141652 KB Output is correct
19 Correct 65 ms 141776 KB Output is correct
20 Correct 68 ms 141652 KB Output is correct
21 Correct 62 ms 141648 KB Output is correct
22 Correct 63 ms 141772 KB Output is correct
23 Correct 66 ms 141648 KB Output is correct
24 Correct 65 ms 141648 KB Output is correct
25 Correct 64 ms 141648 KB Output is correct
26 Correct 65 ms 141652 KB Output is correct
27 Correct 66 ms 141652 KB Output is correct
28 Correct 64 ms 141652 KB Output is correct
29 Correct 66 ms 141724 KB Output is correct
30 Correct 64 ms 141648 KB Output is correct
31 Correct 1478 ms 209344 KB Output is correct
32 Correct 102 ms 145488 KB Output is correct
33 Correct 1348 ms 207420 KB Output is correct
34 Correct 1363 ms 207840 KB Output is correct
35 Correct 1455 ms 208700 KB Output is correct
36 Correct 1483 ms 209768 KB Output is correct
37 Correct 1062 ms 201704 KB Output is correct
38 Correct 1028 ms 201332 KB Output is correct
39 Correct 683 ms 191728 KB Output is correct
40 Correct 769 ms 193900 KB Output is correct
41 Correct 952 ms 197968 KB Output is correct
42 Correct 972 ms 198632 KB Output is correct
43 Correct 97 ms 147244 KB Output is correct
44 Correct 915 ms 197384 KB Output is correct
45 Correct 759 ms 191728 KB Output is correct
46 Correct 524 ms 183100 KB Output is correct
47 Correct 400 ms 180460 KB Output is correct
48 Correct 361 ms 178672 KB Output is correct
49 Correct 569 ms 185460 KB Output is correct
50 Correct 770 ms 195276 KB Output is correct
51 Correct 500 ms 182932 KB Output is correct
52 Correct 1087 ms 195992 KB Output is correct
53 Correct 980 ms 193972 KB Output is correct
54 Correct 1430 ms 205524 KB Output is correct
55 Correct 1213 ms 202612 KB Output is correct
56 Correct 1238 ms 202812 KB Output is correct
57 Correct 1020 ms 199040 KB Output is correct
58 Correct 1065 ms 199744 KB Output is correct
59 Correct 1106 ms 200652 KB Output is correct
60 Correct 1002 ms 199140 KB Output is correct
61 Correct 193 ms 171448 KB Output is correct
62 Correct 1146 ms 199668 KB Output is correct
63 Correct 1340 ms 204328 KB Output is correct
64 Correct 1384 ms 206748 KB Output is correct
65 Correct 1359 ms 207664 KB Output is correct
66 Correct 1071 ms 201900 KB Output is correct
67 Correct 419 ms 176120 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 141464 KB Output is correct
2 Correct 60 ms 141396 KB Output is correct
3 Correct 64 ms 141392 KB Output is correct
4 Correct 66 ms 141392 KB Output is correct
5 Correct 65 ms 141560 KB Output is correct
6 Correct 65 ms 141648 KB Output is correct
7 Correct 65 ms 141648 KB Output is correct
8 Correct 66 ms 141680 KB Output is correct
9 Correct 64 ms 141660 KB Output is correct
10 Correct 67 ms 141652 KB Output is correct
11 Correct 64 ms 141616 KB Output is correct
12 Correct 64 ms 141648 KB Output is correct
13 Correct 64 ms 141684 KB Output is correct
14 Correct 63 ms 141704 KB Output is correct
15 Correct 64 ms 141744 KB Output is correct
16 Correct 64 ms 141648 KB Output is correct
17 Correct 67 ms 141648 KB Output is correct
18 Correct 64 ms 141652 KB Output is correct
19 Correct 65 ms 141776 KB Output is correct
20 Correct 68 ms 141652 KB Output is correct
21 Correct 62 ms 141648 KB Output is correct
22 Correct 63 ms 141772 KB Output is correct
23 Correct 66 ms 141648 KB Output is correct
24 Correct 65 ms 141648 KB Output is correct
25 Correct 64 ms 141648 KB Output is correct
26 Correct 65 ms 141652 KB Output is correct
27 Correct 66 ms 141652 KB Output is correct
28 Correct 64 ms 141652 KB Output is correct
29 Correct 66 ms 141724 KB Output is correct
30 Correct 64 ms 141648 KB Output is correct
31 Correct 1478 ms 209344 KB Output is correct
32 Correct 102 ms 145488 KB Output is correct
33 Correct 1348 ms 207420 KB Output is correct
34 Correct 1363 ms 207840 KB Output is correct
35 Correct 1455 ms 208700 KB Output is correct
36 Correct 1483 ms 209768 KB Output is correct
37 Correct 1062 ms 201704 KB Output is correct
38 Correct 1028 ms 201332 KB Output is correct
39 Correct 683 ms 191728 KB Output is correct
40 Correct 769 ms 193900 KB Output is correct
41 Correct 952 ms 197968 KB Output is correct
42 Correct 972 ms 198632 KB Output is correct
43 Correct 97 ms 147244 KB Output is correct
44 Correct 915 ms 197384 KB Output is correct
45 Correct 759 ms 191728 KB Output is correct
46 Correct 524 ms 183100 KB Output is correct
47 Correct 400 ms 180460 KB Output is correct
48 Correct 361 ms 178672 KB Output is correct
49 Correct 569 ms 185460 KB Output is correct
50 Correct 770 ms 195276 KB Output is correct
51 Correct 500 ms 182932 KB Output is correct
52 Correct 1616 ms 312672 KB Output is correct
53 Correct 1531 ms 313800 KB Output is correct
54 Correct 1534 ms 301436 KB Output is correct
55 Correct 1631 ms 309592 KB Output is correct
56 Correct 1563 ms 314396 KB Output is correct
57 Correct 1513 ms 313212 KB Output is correct
58 Correct 1546 ms 301456 KB Output is correct
59 Correct 1721 ms 309076 KB Output is correct
60 Correct 1672 ms 314168 KB Output is correct
61 Correct 1670 ms 316056 KB Output is correct
62 Correct 1166 ms 310704 KB Output is correct
63 Correct 1210 ms 314552 KB Output is correct
64 Execution timed out 5042 ms 416988 KB Time limit exceeded
65 Halted 0 ms 0 KB -