Submission #313607

#	Time	Username	Problem	Language	Result	Execution time	Memory
313607		gurkot	Interval Collection (CCO20_day2problem2)	C++14	25 / 25	3963 ms	245100 KiB

Main

#include <iostream>
#include <set>
using namespace std;

multiset <int> setl,setr;
multiset <int> msl[1000001],msr[1000001];
struct Node { int maxl,minr,ans;} tree[4000001];
const int TS=1000000; 
int q,a,b;
char ch;
    
void update_L(int u,int a,int b,int pos,int val) {
 //cout<<a<<"   -L-   "<<b<<" u="<<u<<endl;
 if(a==b) {
  tree[u].maxl=val; tree[u].ans=tree[u].minr-val; 
  //cout<<"tree_L: ans="<<tree[u].ans<<endl;
  //cout<<a<<"   -L-   "<<b<<" u="<<u<<endl;
  return;
 } 
 int c=(a+b)/2;
 int l,r;
 l=2*u; r=l+1;
 if(pos<=c) update_L(l,a,c,pos,val);
       else update_L(r, c+1,b,pos,val);
 
 tree[u].maxl=max(tree[l].maxl,tree[r].maxl);
 tree[u].minr=min(tree[l].minr,tree[r].minr);      
 tree[u].ans=min(tree[l].ans,tree[r].ans);
 tree[u].ans=min(tree[u].ans,tree[r].minr-tree[l].maxl);       
}


void update_R(int u,int a,int b,int pos,int val) {
 //cout<<a<<"   -R-   "<<b<<" u="<<u<<endl;
 if(a==b) {
  tree[u].minr=val;	tree[u].ans=val-tree[u].maxl;  
  //cout<<"tree_R: ans="<<tree[u].ans<<endl;
  //cout<<a<<"   -R-   "<<b<<" u="<<u<<endl;
  return;
 } 
 int c=(a+b)/2;
 int l,r;
 l=2*u; r=l+1;
 if(pos<=c) {
  update_R(l,a,  c,pos,val);
  tree[u].maxl=max(tree[l].maxl,tree[r].maxl);
  tree[u].minr=min(tree[l].minr,tree[r].minr);
  
 } else {
  update_R(r,c+1,b,pos,val);
  tree[u].maxl=max(tree[l].maxl,tree[r].maxl);
  tree[u].minr=min(tree[l].minr,tree[r].minr);  
 }
  
  
      
 tree[u].ans=min(tree[l].ans,tree[r].ans);
 tree[u].ans=min(tree[u].ans,tree[r].minr-tree[l].maxl);       
}

main(){ 
 for (int i=1;i<=4000000;i++){ 
   tree[i].maxl=-10000000, tree[i].minr=10000000;
   tree[i].ans=2000001;
 }
   
 ios::sync_with_stdio(false);
 cin>>q;
 while(q--) {
  cin>>ch>>a>>b;
  if(ch=='A') {
   setl.insert(a); setr.insert(b);
   msl[b].insert(a); msr[a].insert(b); 
   
   //cout<<*msl[b].rbegin()<<"  - ok1- "<<*msr[a].begin()<<endl;   
   //system("pause");
                
   
   update_R(1,1,TS,a,*msr[a].begin());
   update_L(1,1,TS,b,*msl[b].rbegin());
   
   
  } else { 
   setl.erase(setl.find(a));        setr.erase(setr.find(b));
   msl[b].erase(msl[b].find(a));    msr[a].erase(msr[a].find(b));
   
   
     
   if (msr[a].size()==0) update_R(1,1,TS,a,10000000);
                   else  update_R(1,1,TS,a,*msr[a].begin());
                   
   if (msl[b].size()==0) update_L(1,1,TS,b,-10000000);
                   else  update_L(1,1,TS,b,*msl[b].rbegin());
   
  }
  
  a=*setl.rbegin();  b=*setr.begin(); 
   //cout<<"a="<<a<<" <- ok4 -> "<<"b="<<b<<endl;
   
  /* 
   cout<<"tree\n";
   for (int i=1;i<10;i++) 
    cout<<"node "<<i<<":    "<<
	  tree[i].maxl<<" "<<tree[i].minr<<"  ans="<<tree[i].ans<<endl;
   system("pause");
  */
           
  if(a<b)   cout<<(*msr[a].begin()-*msl[b].rbegin())<<endl;
     else   cout<<tree[1].ans<<endl;  
 }//while
}

Compilation message (stderr)

Main.cpp:61:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   61 | main(){
      |      ^

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 4 / 4
• Subtask 5: 3 / 3