제출 #293739

#제출 시각아이디문제언어결과실행 시간메모리
293739crossing0verInterval Collection (CCO20_day2problem2)C++17
0 / 25
2455 ms342924 KiB
#include<bits/stdc++.h> #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]; 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); } // x >= PX, y-minimal // x <= PX, y max int cans=INT_MAX; int t[2][4*N],timer; int *H[130000000]; int val[130000000]; void change(int&x,int c) { ++timer; H[timer] = &x; val[timer] = x; x = c; } void rollback() { (*H[timer]) = val[timer]; timer--; } bool type; int VAL,pos; void add(int v,int tl,int tr) { if (tl == tr) { if (type == 0) change(t[0][v],min(t[0][v],VAL)); else change(t[1][v],max(t[1][v],VAL)); // t[0][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 == 0) 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])); //t[v] = t[v*2] + t[v*2+1]; } int L,R; int get(int v,int tl,int tr) { 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 == 0) 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)); } void dfs(int v,int tl,int tr) { int in_ans = cans; int start_time = timer; if (timer > 60000000) { while(true) { } } for (auto i1 : Q[v]) { int l = i1.fi; int r = i1.se; type = 0; L = r; R = 1e6; type = 0; if (cans > r - l) cans = min(cans, -l + get(1,1,1e6)); L = 1; R = l;type = 1; if (cans > r - l) cans = min(cans, r - get(1,1,1e6)); pos = l; VAL = r; type = 0; add(1,1,1e6); // l-ze patara r-ebshi udidesi l, r-ze did l-ebshi umciresi r pos = r; VAL = l; type = 1; add(1,1,1e6); } if (tl != tr) { int tm = (tl + tr)/2; dfs(v*2,tl,tm); dfs(v*2+1,tm+1,tr); }else { if (F[tl]) ANS[tl] = cans; } while(start_time != timer) { rollback(); }/* for (auto i1 : Q[v]) { int l = i1.fi; int r = i1.se; // PX = r; // PY = r; // cans = min(cans, -l + get_x(1,1,1e6); // PX = l; // cans = min(cans, r - GET_X(1,1,1e6)); PX = l; PY = r; upd_x(1,1,1e6,-1); // l-ze patara r-ebshi udidesi l, r-ze did l-ebshi umciresi r PX = r; PY = l; UPD_X(1,1,1e6,-1); }*/ cans = in_ans; } main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int q; cin >> q; multiset<int> L,R; multiset<int> AL[1000004],AR[1000004]; // map<pii,vector<int> > cnt; for (int i = 0; i < 4*1000000;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); // L.insert(l); // R.insert(r); // AR[l].insert(r); // AL[r].insert(l); }else { qer(1,1,q,*cnt[id].begin(),i-1,l,r); cnt[id].erase(cnt[id].begin());} /* if (!AL[r].count(l)) { while(true) { } } AL[r].erase(AL[r].find(l)); if (!AR[l].count(r)) { while(true) { } } AR[l].erase(AR[l].find(r)); if (!L.count(l)) { while(true) { } } L.erase(L.find(l)); if (!R.count(r)) { while(true) { } } R.erase(R.find(r)); } if (L.empty() || R.empty()) { while(true) { } } l = *L.rbegin(); r = *R.begin(); int len = max(0,r - l); if (len) { int l1 = l, r1 = r; if (AR[l1].empty() || AL[r1].empty()) { while(true) { } } r = *AR[l1].begin(); l = *AL[r1].rbegin(); ANS[i] = r-l; }else { F[i] = 1; }}*/ 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'; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:145:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  145 | main() {
      |      ^
Main.cpp: In function 'int main()':
Main.cpp:168: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]
  168 |     for (int i = 0; i < t.size(); i++) {
      |                     ~~^~~~~~~~~~
Main.cpp:235: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]
  235 |         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...