Submission #293875

#TimeUsernameProblemLanguageResultExecution timeMemory
293875crossing0verInterval Collection (CCO20_day2problem2)C++17
0 / 25
798 ms1048580 KiB
#include<bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #define ll long long #define vi vector<int> #define pii pair<int,int> #define all(x) x.begin(),x.end() #define fi first #define se second #define pb push_back using namespace std; const int N = 1e6+6,inf = 1e8; int F[N],ANS[N]; vector<pii> Q[N*4]; int l1,r1,QL,QR; void qer(int v,int tl,int tr) { if (l1 > tr || r1 < tl) return; if (l1 <= tl && r1 >= tr) { Q[v].pb({QL,QR}); return; } int tm = (tl + tr)/2; qer(v*2,tl,tm); qer(v*2+1,tm+1,tr); } int cans=INT_MAX; int t[2][4*N],timer; int *H[100000000]; int val[100000000]; void change(int&x,int c) { H[++timer] = &x; val[timer] = x; x = c; } void rollback() { (*H[timer--]) = val[timer]; } bool type; int VAL,pos,L,R; int BIT[2][N]; const int REV = 1e6+1; void add(int v=1,int tl=1,int tr=1e6) { if (tl == tr) { if (!type) { if (VAL < t[0][v]) change(t[0][v],VAL); } else if (VAL > t[1][v]) change(t[1][v],VAL); return; } int tm = (tl + tr)/2; if (pos <= tm) add(v*2,tl,tm); else add(v*2+1,tm+1,tr); if (!type) change(t[0][v],min(t[0][v*2],t[0][v*2+1])); else change(t[1][v],max(t[1][v*2],t[1][v*2+1])); } void add1(int pos,int val,bool type) { if (type == 1) for (;pos <= 1e6; pos += pos&-pos) if (BIT[1][pos] < val) change(BIT[1][pos],val); else { for (;pos <= 1e6; pos += pos&-pos) if (BIT[0][pos] > val) change(BIT[0][pos],val); } } int get1(int pos,bool type) { if (type == 0) { int s = inf; for (;pos;pos -= pos&-pos) s = min(s,BIT[0][pos]); return s; }else { int s = -inf; for (;pos;pos -= pos&-pos) s = max(s,BIT[1][pos]); return s; } } int get(int v=1,int tl=1,int tr=1e6) { if (L> tr || R < tl) { if (type == 0) return inf; else return -inf; } if (L <= tl && R >= tr) return t[type][v]; int tm = (tl + tr)/2; if (!type) return min(get(v*2,tl,tm),get(v*2+1,tm+1,tr)); else return max(get(v*2,tl,tm),get(v*2+1,tm+1,tr)); } int L1=-inf,R1=inf,AR1[N],AL1[N],HANS=inf; void dfs(int v,int tl,int tr) { int in_ans = cans; int start_time = timer; for (auto& i1 : Q[v]) { int l = i1.fi; int r = i1.se; if (R1 > r) change(R1,r); if (L1 < l) change(L1,l); if (AR1[l] > r) change(AR1[l],r); if (AL1[r] < l) change(AL1[r],l); { int l2 = L1; int r2 = R1; int len = max(0,r2 - l2); if (len) { int r3 = AR1[l2]; int l3 = AL1[r2]; change(HANS,r3-l3); pos = l; VAL = r; type = 0; // add(1e6); // l-ze patara r-ebshi udidesi l, r-ze did l-ebshi umciresi r add(REV - pos,r,0); pos = r; VAL = l; type = 1; // add(); add(pos,VAL,1); continue; } } L = r; R = 1e6; type = 0; if (cans > r - l) { cans = min(cans, -l + get(REV - L,0)); } L = 1; R = l;type = 1; if (cans > r - l) cans = min(cans, r - get(R,1)); pos = l; VAL = r; type = 0; // add(1e6); // l-ze patara r-ebshi udidesi l, r-ze did l-ebshi umciresi r // add1(REV - pos,r,0); pos = r; VAL = l; type = 1; // add(); // add1(pos,VAL,1); } if (tl != tr) { int tm = (tl + tr)/2; dfs(v*2,tl,tm); dfs(v*2+1,tm+1,tr); }else { if (cans > 1000000) ANS[tl] = HANS; else ANS[tl] = cans; } while(start_time != timer) rollback(); cans = in_ans; } main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int q; cin >> q; for (int i = 0; i < N; i++) AR1[i] = BIT[0][i] = inf,AL1[i] = BIT[1][i]=-inf; for (int i = 0; i < 4*N;i ++) t[0][i] = inf, t[1][i] = -inf; vector<pair<pii,char> > query(q+1); vector<pii> t(q); for (int i = 1; i <= q; i++) { char c; int l,r; cin >> c >> l >> r; query[i] = {{l,r},c}; t[i-1] = {l,r}; } sort(all(t)); t.resize(unique(all(t)) - t.begin()); map<pii,int> ID; for (int i = 0; i < t.size(); i++) { ID[t[i]] = i; } set<int> cnt[1000005]; for (int i = 1; i <= q; i++) { char c= query[i].se; int l = query[i].fi.fi; int r = query[i].fi.se; int id = ID[{l,r}]; if (c == 'A') cnt[id].insert(i); else { l1=*cnt[id].begin(); r1 = i-1; QL= l; QR = r; qer(1,1,q); cnt[id].erase(cnt[id].begin()); } F[i] = 1; } for (int i= 0; i < t.size(); i++) for (int j : cnt[i]) { l1 = j; r1 = q; QL = t[i].fi; QR = t[i].se; qer(1,1,q); } dfs(1,1,q); for (int i = 1; i <= q; i++) cout << ANS[i] <<'\n'; }

Compilation message (stderr)

Main.cpp: In function 'void rollback()':
Main.cpp:38:14: warning: operation on 'timer' may be undefined [-Wsequence-point]
   38 |     (*H[timer--]) = val[timer];
      |         ~~~~~^~
Main.cpp:38:14: warning: operation on 'timer' may be undefined [-Wsequence-point]
Main.cpp: In function 'void add1(int, int, bool)':
Main.cpp:65:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   65 |     if (type == 1)
      |        ^
Main.cpp: In function 'int get1(int, bool)':
Main.cpp:78:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   78 |     for (;pos;pos -= pos&-pos)
      |     ^~~
Main.cpp:80:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   80 |         return s;
      |         ^~~~~~
Main.cpp:83:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   83 |     for (;pos;pos -= pos&-pos)
      |     ^~~
Main.cpp:85:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   85 |         return s;
      |         ^~~~~~
Main.cpp: At global scope:
Main.cpp:174:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  174 | main() {
      |      ^
Main.cpp: In function 'int main()':
Main.cpp:196:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |     for (int i = 0; i < t.size(); i++) {
      |                     ~~^~~~~~~~~~
Main.cpp:217:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |         for (int i= 0; i < t.size(); i++)
      |                        ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...