oj.uz

Submission #674467

# Submission time Handle Problem Language Result Execution time Memory
674467 2022-12-24T11:30:16 Z MohammadAghil New Home (APIO18_new_home) C++17
47 / 100
 5000 ms 489156 KB 
      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
 using namespace std;
  typedef long long ll;
   typedef pair<ll, ll> pp;
     #define per(i,r,l) for(int i = (r); i >= (l); i--)
       #define rep(i,l,r) for(int i = (l); i < (r); i++)
          #define all(x) begin(x), end(x)
             #define sz(x) (int)(x).size()
                 #define pb push_back
                     #define ss second
                          #define ff first
                                  void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGEs
          #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
     #else
          #define er(args ...) 0
     #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 6e5 + 5, lg = 22, inf = ll(2e8) + 5, p = 9973;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}

multiset<int> seg[maxn<<2];
vector<pp> query[maxn];
multiset<int> pos[maxn];
vector<int> cmp;
int ans[maxn];

int less_id(int x){
     return upper_bound(all(cmp), x) - begin(cmp) - 1;
}

void add(int l, int r, int t, int x = 1, int lx = 0, int rx = maxn){
     if(l <= lx && r >= rx){
          seg[x].insert(t);
          return;
     }
     int mid = (lx + rx)>>1;
     if(l < mid) add(l, r, t, x<<1, lx, mid);
     if(mid < r) add(l, r, t, x<<1|1, mid, rx);
}

void rem(int l, int r, int t, int x = 1, int lx = 0, int rx = maxn){
     if(l <= lx && r >= rx){
          seg[x].erase(seg[x].find(t));
          return;
     }
     int mid = (lx + rx)>>1;
     if(l < mid) rem(l, r, t, x<<1, lx, mid);
     if(mid < r) rem(l, r, t, x<<1|1, mid, rx);
}

pp get(int i, int x = 1, int lx = 0, int rx = maxn){
     pp res = {sz(cmp)-1, 0};
     if(sz(seg[x])) res.ff = *begin(seg[x]), res.ss = *prev(end(seg[x]));
     if(lx + 1 == rx){
          return res;
     }
     int mid = (lx + rx)>>1;
     pp ret;
     if(i < mid) ret = get(i, x<<1, lx, mid);
     else ret = get(i, x<<1|1, mid, rx);
     res.ff = min(res.ff, ret.ff), res.ss = max(res.ss, ret.ss);
     return res;
}

void add_t(int a, int b){
     int mid = less_id((cmp[a] + cmp[b])/2);
     // er(a, b, mid);
     if(mid >= a) add(a, mid + 1, a);
     if(mid < b) add(mid + 1, b + 1, b);
}

void rem_t(int a, int b){
     int mid = less_id((cmp[a] + cmp[b])/2);
     // er(a, b, mid, (cmp[a]+cmp[b])/2);
     if(mid >= a) rem(a, mid + 1, a);
     if(mid < b) rem(mid + 1, b + 1, b);
}

void add_t(pp t){
     auto[x, tp] = t; x = less_id(x);
     auto it = pos[tp].upper_bound(x);
     // er(x, tp, *it, *prev(it));
     rem_t(*prev(it), *it);
     add_t(*prev(it), x);
     add_t(x, *it);
     pos[tp].insert(x);
}

void rem_t(pp t){
     auto[x, tp] = t; x = less_id(x);
     auto it = pos[tp].lower_bound(x);
     rem_t(x, *next(it));
     rem_t(*prev(it), x);
     add_t(*prev(it), *next(it));
     pos[tp].erase(pos[tp].find(x));
}

int main(){ IOS();
     int n, k, q; cin >> n >> k >> q;
     map<int, pair<vector<pair<pp, bool>>, vector<pp>>> mp;
     cmp = {-inf, inf};
     rep(i,0,n){
          int x, t, l, r; cin >> x >> t >> l >> r;
          mp[l].ff.pb({{x, t}, true});
          mp[r + 1].ff.pb({{x, t}, false});
          cmp.pb(x);
     }
     rep(i,0,q){
          int l, y; cin >> l >> y;
          cmp.pb(l);
          mp[y].ss.pb({l, i});
     }
     sort(all(cmp)), cmp.erase(unique(all(cmp)), end(cmp));
     rep(i,1,k+1) pos[i].insert(0), pos[i].insert(sz(cmp)-1), add_t(0, sz(cmp)-1);
     // for(int c: cmp) er(c);
     for(auto[_, tmp]: mp){
          auto[upd, query] = tmp;
          // er(_);
          for(auto[t, is]: upd){
               if(is) add_t(t);
               else rem_t(t);
          }
          // er(_);
          for(auto[l, id]: query){
               auto[mn, mx] = get(less_id(l));
               // er(l, id, mn, mx);
               if(!mn || mx == sz(cmp)-1) ans[id] = -1;
               else ans[id] = max(cmp[mx] - l, l - cmp[mn]);
          }
          // er(_);
     }
     rep(i,0,q) cout << ans[i] << '\n';
     return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 155216 KB Output is correct
2 Correct 72 ms 155244 KB Output is correct
3 Correct 69 ms 155220 KB Output is correct
4 Correct 70 ms 155236 KB Output is correct
5 Correct 71 ms 155316 KB Output is correct
6 Correct 80 ms 155440 KB Output is correct
7 Correct 79 ms 155776 KB Output is correct
8 Correct 75 ms 155676 KB Output is correct
9 Correct 79 ms 155912 KB Output is correct
10 Correct 81 ms 155596 KB Output is correct
11 Correct 72 ms 155400 KB Output is correct
12 Correct 71 ms 155504 KB Output is correct
13 Correct 74 ms 155428 KB Output is correct
14 Correct 71 ms 155444 KB Output is correct
15 Correct 84 ms 155636 KB Output is correct
16 Correct 77 ms 155652 KB Output is correct
17 Correct 72 ms 155504 KB Output is correct
18 Correct 76 ms 155672 KB Output is correct
19 Correct 80 ms 155704 KB Output is correct
20 Correct 78 ms 155548 KB Output is correct
21 Correct 71 ms 155484 KB Output is correct
22 Correct 75 ms 155948 KB Output is correct
23 Correct 76 ms 155800 KB Output is correct
24 Correct 74 ms 155728 KB Output is correct
25 Correct 84 ms 155556 KB Output is correct
26 Correct 73 ms 155376 KB Output is correct
27 Correct 72 ms 155364 KB Output is correct
28 Correct 77 ms 155456 KB Output is correct
29 Correct 84 ms 155468 KB Output is correct
30 Correct 72 ms 155500 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 155216 KB Output is correct
2 Correct 72 ms 155244 KB Output is correct
3 Correct 69 ms 155220 KB Output is correct
4 Correct 70 ms 155236 KB Output is correct
5 Correct 71 ms 155316 KB Output is correct
6 Correct 80 ms 155440 KB Output is correct
7 Correct 79 ms 155776 KB Output is correct
8 Correct 75 ms 155676 KB Output is correct
9 Correct 79 ms 155912 KB Output is correct
10 Correct 81 ms 155596 KB Output is correct
11 Correct 72 ms 155400 KB Output is correct
12 Correct 71 ms 155504 KB Output is correct
13 Correct 74 ms 155428 KB Output is correct
14 Correct 71 ms 155444 KB Output is correct
15 Correct 84 ms 155636 KB Output is correct
16 Correct 77 ms 155652 KB Output is correct
17 Correct 72 ms 155504 KB Output is correct
18 Correct 76 ms 155672 KB Output is correct
19 Correct 80 ms 155704 KB Output is correct
20 Correct 78 ms 155548 KB Output is correct
21 Correct 71 ms 155484 KB Output is correct
22 Correct 75 ms 155948 KB Output is correct
23 Correct 76 ms 155800 KB Output is correct
24 Correct 74 ms 155728 KB Output is correct
25 Correct 84 ms 155556 KB Output is correct
26 Correct 73 ms 155376 KB Output is correct
27 Correct 72 ms 155364 KB Output is correct
28 Correct 77 ms 155456 KB Output is correct
29 Correct 84 ms 155468 KB Output is correct
30 Correct 72 ms 155500 KB Output is correct
31 Correct 2489 ms 229112 KB Output is correct
32 Correct 292 ms 164572 KB Output is correct
33 Correct 1042 ms 191660 KB Output is correct
34 Correct 2465 ms 202432 KB Output is correct
35 Correct 1988 ms 220404 KB Output is correct
36 Correct 1022 ms 202368 KB Output is correct
37 Correct 879 ms 184264 KB Output is correct
38 Correct 526 ms 183056 KB Output is correct
39 Correct 478 ms 181848 KB Output is correct
40 Correct 470 ms 181896 KB Output is correct
41 Correct 1165 ms 182888 KB Output is correct
42 Correct 1238 ms 183032 KB Output is correct
43 Correct 240 ms 170752 KB Output is correct
44 Correct 1172 ms 182824 KB Output is correct
45 Correct 938 ms 182168 KB Output is correct
46 Correct 704 ms 181956 KB Output is correct
47 Correct 521 ms 180904 KB Output is correct
48 Correct 468 ms 180768 KB Output is correct
49 Correct 613 ms 181412 KB Output is correct
50 Correct 950 ms 182156 KB Output is correct
51 Correct 584 ms 181132 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 155216 KB Output is correct
2 Correct 72 ms 155244 KB Output is correct
3 Correct 69 ms 155220 KB Output is correct
4 Correct 70 ms 155236 KB Output is correct
5 Correct 71 ms 155316 KB Output is correct
6 Correct 80 ms 155440 KB Output is correct
7 Correct 79 ms 155776 KB Output is correct
8 Correct 75 ms 155676 KB Output is correct
9 Correct 79 ms 155912 KB Output is correct
10 Correct 81 ms 155596 KB Output is correct
11 Correct 72 ms 155400 KB Output is correct
12 Correct 71 ms 155504 KB Output is correct
13 Correct 74 ms 155428 KB Output is correct
14 Correct 71 ms 155444 KB Output is correct
15 Correct 84 ms 155636 KB Output is correct
16 Correct 77 ms 155652 KB Output is correct
17 Correct 72 ms 155504 KB Output is correct
18 Correct 76 ms 155672 KB Output is correct
19 Correct 80 ms 155704 KB Output is correct
20 Correct 78 ms 155548 KB Output is correct
21 Correct 71 ms 155484 KB Output is correct
22 Correct 75 ms 155948 KB Output is correct
23 Correct 76 ms 155800 KB Output is correct
24 Correct 74 ms 155728 KB Output is correct
25 Correct 84 ms 155556 KB Output is correct
26 Correct 73 ms 155376 KB Output is correct
27 Correct 72 ms 155364 KB Output is correct
28 Correct 77 ms 155456 KB Output is correct
29 Correct 84 ms 155468 KB Output is correct
30 Correct 72 ms 155500 KB Output is correct
31 Correct 2489 ms 229112 KB Output is correct
32 Correct 292 ms 164572 KB Output is correct
33 Correct 1042 ms 191660 KB Output is correct
34 Correct 2465 ms 202432 KB Output is correct
35 Correct 1988 ms 220404 KB Output is correct
36 Correct 1022 ms 202368 KB Output is correct
37 Correct 879 ms 184264 KB Output is correct
38 Correct 526 ms 183056 KB Output is correct
39 Correct 478 ms 181848 KB Output is correct
40 Correct 470 ms 181896 KB Output is correct
41 Correct 1165 ms 182888 KB Output is correct
42 Correct 1238 ms 183032 KB Output is correct
43 Correct 240 ms 170752 KB Output is correct
44 Correct 1172 ms 182824 KB Output is correct
45 Correct 938 ms 182168 KB Output is correct
46 Correct 704 ms 181956 KB Output is correct
47 Correct 521 ms 180904 KB Output is correct
48 Correct 468 ms 180768 KB Output is correct
49 Correct 613 ms 181412 KB Output is correct
50 Correct 950 ms 182156 KB Output is correct
51 Correct 584 ms 181132 KB Output is correct
52 Correct 2885 ms 301376 KB Output is correct
53 Correct 2895 ms 272192 KB Output is correct
54 Correct 3676 ms 272032 KB Output is correct
55 Correct 2332 ms 223264 KB Output is correct
56 Correct 2356 ms 240420 KB Output is correct
57 Correct 1806 ms 194628 KB Output is correct
58 Correct 2576 ms 223556 KB Output is correct
59 Correct 2649 ms 246316 KB Output is correct
60 Correct 2090 ms 195268 KB Output is correct
61 Correct 378 ms 187740 KB Output is correct
62 Correct 2871 ms 301360 KB Output is correct
63 Correct 3274 ms 265000 KB Output is correct
64 Correct 3510 ms 247524 KB Output is correct
65 Correct 3496 ms 203972 KB Output is correct
66 Correct 1397 ms 184128 KB Output is correct
67 Correct 843 ms 168836 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 155216 KB Output is correct
2 Correct 72 ms 155244 KB Output is correct
3 Correct 69 ms 155220 KB Output is correct
4 Correct 70 ms 155236 KB Output is correct
5 Correct 71 ms 155316 KB Output is correct
6 Correct 80 ms 155440 KB Output is correct
7 Correct 79 ms 155776 KB Output is correct
8 Correct 75 ms 155676 KB Output is correct
9 Correct 79 ms 155912 KB Output is correct
10 Correct 81 ms 155596 KB Output is correct
11 Correct 72 ms 155400 KB Output is correct
12 Correct 71 ms 155504 KB Output is correct
13 Correct 74 ms 155428 KB Output is correct
14 Correct 71 ms 155444 KB Output is correct
15 Correct 84 ms 155636 KB Output is correct
16 Correct 77 ms 155652 KB Output is correct
17 Correct 72 ms 155504 KB Output is correct
18 Correct 76 ms 155672 KB Output is correct
19 Correct 80 ms 155704 KB Output is correct
20 Correct 78 ms 155548 KB Output is correct
21 Correct 71 ms 155484 KB Output is correct
22 Correct 75 ms 155948 KB Output is correct
23 Correct 76 ms 155800 KB Output is correct
24 Correct 74 ms 155728 KB Output is correct
25 Correct 84 ms 155556 KB Output is correct
26 Correct 73 ms 155376 KB Output is correct
27 Correct 72 ms 155364 KB Output is correct
28 Correct 77 ms 155456 KB Output is correct
29 Correct 84 ms 155468 KB Output is correct
30 Correct 72 ms 155500 KB Output is correct
31 Correct 2489 ms 229112 KB Output is correct
32 Correct 292 ms 164572 KB Output is correct
33 Correct 1042 ms 191660 KB Output is correct
34 Correct 2465 ms 202432 KB Output is correct
35 Correct 1988 ms 220404 KB Output is correct
36 Correct 1022 ms 202368 KB Output is correct
37 Correct 879 ms 184264 KB Output is correct
38 Correct 526 ms 183056 KB Output is correct
39 Correct 478 ms 181848 KB Output is correct
40 Correct 470 ms 181896 KB Output is correct
41 Correct 1165 ms 182888 KB Output is correct
42 Correct 1238 ms 183032 KB Output is correct
43 Correct 240 ms 170752 KB Output is correct
44 Correct 1172 ms 182824 KB Output is correct
45 Correct 938 ms 182168 KB Output is correct
46 Correct 704 ms 181956 KB Output is correct
47 Correct 521 ms 180904 KB Output is correct
48 Correct 468 ms 180768 KB Output is correct
49 Correct 613 ms 181412 KB Output is correct
50 Correct 950 ms 182156 KB Output is correct
51 Correct 584 ms 181132 KB Output is correct
52 Execution timed out 5082 ms 489156 KB Time limit exceeded
53 Halted 0 ms 0 KB -