Submission #293815

#TimeUsernameProblemLanguageResultExecution timeMemory
293815crossing0verInterval Collection (CCO20_day2problem2)C++17
22 / 25
7083 ms567652 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]; void qer(int v,int tl,int tr,int l,int r,int QL,int QR) { if (l > tr || r < tl) return; if (l <= tl && r >= tr) { Q[v].pb({QL,QR}); return; } int tm = (tl + tr)/2; qer(v*2,tl,tm,l,r,QL,QR); qer(v*2+1,tm+1,tr,l,r,QL,QR); } int cans=INT_MAX; int t[2][4*N],timer; int *H[61000000]; int val[61000000]; 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; void add(int v=1,int tl=1,int tr=1e6) { if (tl == tr) { if (!type) change(t[0][v],min(t[0][v],VAL)); else change(t[1][v],max(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])); } 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; change(R1,min(R1,r)); change(L1,max(L1,l)); change(AR1[l],min(AR1[l],r)); change(AL1[r],max(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(); // l-ze patara r-ebshi udidesi l, r-ze did l-ebshi umciresi r pos = r; VAL = l; type = 1; add(); continue; } } L = r; R = 1e6; type = 0; if (cans > r - l) cans = min(cans, -l + get()); L = 1; R = l;type = 1; if (cans > r - l) cans = min(cans, r - get()); pos = l; VAL = r; type = 0; add(); // l-ze patara r-ebshi udidesi l, r-ze did l-ebshi umciresi r pos = r; VAL = l; type = 1; add(); } 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] = inf,AL1[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 { qer(1,1,q,*cnt[id].begin(),i-1,l,r); cnt[id].erase(cnt[id].begin()); } F[i] = 1; } for (int i= 0; i < t.size(); i++) for (int j : cnt[i]) qer(1,1,q,j,q,t[i].fi,t[i].se); 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:37:14: warning: operation on 'timer' may be undefined [-Wsequence-point]
   37 |     (*H[timer--]) = val[timer];
      |         ~~~~~^~
Main.cpp:37:14: warning: operation on 'timer' may be undefined [-Wsequence-point]
Main.cpp: At global scope:
Main.cpp:134:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  134 | main() {
      |      ^
Main.cpp: In function 'int main()':
Main.cpp:156: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]
  156 |     for (int i = 0; i < t.size(); i++) {
      |                     ~~^~~~~~~~~~
Main.cpp:173: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]
  173 |         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...