제출 #312630

#제출 시각아이디문제언어결과실행 시간메모리
312630giorgikobInterval Collection (CCO20_day2problem2)C++14
7 / 25
2661 ms283312 KiB
#include<bits/stdc++.h> #define ll long long #define ff first #define ss second #define pb push_back using namespace std; const int N = 1e6+5; struct bla{ bla *left = NULL, *right = NULL; int answer = 1e9; int l = -1; int r = -1; }; multiset<int>b[N],e[N],L,R; inline void go(int x,int y,int &l,int &r,int &answer){ if(x != -1){ if(x == -2) l = -1; else if(l == -1) l = x; else l = max(l, x); } if(y != -1){ if(y == -2) r = -1; else if(r == -1) r = y; else r = min(r, y); } answer = 1e9; if(l != -1 && r != -1){ answer = r - l; } } inline int mn(int x,int y){ if(x == -1) return y; if(y == -1) return x; return min(x,y); } inline int mx(int x,int y){ if(x == -1) return y; if(y == -1) return x; return max(x,y); } inline int get(int y,int x){ if(x == -1 || y == -1){ return 1e9; } return y - x; } inline void upd(bla* &node,int tl,int tr,int pos,int x,int y){ if(tl == tr){ go(x,y,node->l,node->r,node->answer); return ; } int mid = tl + tr; mid >>= 1; if(node->left == NULL)node->left = new bla(); if(node->right == NULL)node->right = new bla(); if(pos <= mid){ upd(node->left,tl,mid,pos,x,y); } else { upd(node->right,mid+1,tr,pos,x,y); } node->l = mx(node->left->l,node->right->l); node->r = mn(node->left->r,node->right->r); node->answer = get(node->right->r, node->left->l); node->answer = min(node->answer, min(node->left->answer, node->right->answer)); } int main(){ ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0); bla* root = new bla(); int q; cin >> q; while(q--){ char c; int l,r; cin >> c >> l >> r; if(c == 'A'){ b[l].insert(r); e[r].insert(l); L.insert(l); R.insert(r); } else { b[l].erase(b[l].find(r)); e[r].erase(e[r].find(l)); L.erase(L.find(l)); R.erase(R.find(r)); } int val; if(b[l].size()) val = *b[l].rbegin(); else val = -2; upd(root,1,N-1,l,-1,val); //cout << val << endl; if(e[r].size()) val = *e[r].rbegin(); else val = -2; upd(root,1,N-1,r,val,-1); //cout << val << endl; if(L.size() == 0){ cout << 0 << endl; continue; } int x = *L.rbegin(); int y = *R.begin(); if(x <= y){ cout << (*b[x].begin() - *e[y].rbegin()) << endl; } else { //cout << "second : "; cout << root->answer << endl; } } }
#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...