Submission #568456

#	Time	Username	Problem	Language	Result	Execution time	Memory
568456		Ahmadsm2005	Interval Collection (CCO20_day2problem2)	C++17	22 / 25	7037 ms	336156 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int N,L,R;
pair<int,int>seg[1<<21],seg2[1<<21];
set<int>SEG[1<<20],SEG2[1<<20];
map<pair<int,int>,int>COUNT;
map<pair<int,int>,set<pair<int,int>>>MP;
multiset<pair<int,int>>GLOBAL; ///{R-L,L}
char C;
pair<int,int>G1(pair<int,int>A,pair<int,int>B){
if(A.first==INT_MAX)
return B;
else if(B.first==INT_MAX)
return A;
if(A.second<B.second)
return A;
else if(A.second==B.second&&A.first>B.first)
return A;
return B;
}
pair<int,int>G2(pair<int,int>A,pair<int,int>B){
if(A.first==INT_MAX)
return B;
else if(B.first==INT_MAX)
return A;
if(A.first>B.first)
return A;
else if(A.first==B.first&&A.second<B.second)
return A;
return B;
}
void updA1(int T,int v,int LL=0,int RR=(1<<20)-1,int idx=0){
if(T==LL&&LL==RR){
SEG[T].insert(v);
seg[idx]={T,*SEG[T].begin()};
return;
}
if((LL+RR)/2>=T)
updA1(T,v,LL,(LL+RR)/2,idx*2+1);
else
updA1(T,v,(LL+RR)/2+1,RR,idx*2+2);
seg[idx]=G1(seg[idx*2+1],seg[idx*2+2]);
}
void updR1(int T,int v,int LL=0,int RR=(1<<20)-1,int idx=0){
if(T==LL&&LL==RR){
SEG[T].erase(v);
if(SEG[T].size())
seg[idx]={T,*SEG[T].begin()};
else
seg[idx]={INT_MAX,INT_MAX};
return;
}
if((LL+RR)/2>=T)
updR1(T,v,LL,(LL+RR)/2,idx*2+1);
else
updR1(T,v,(LL+RR)/2+1,RR,idx*2+2);
seg[idx]=G1(seg[idx*2+1],seg[idx*2+2]);
}
pair<int,int>query1(int L,int R,int LL=0,int RR=(1<<20)-1,int idx=0){
if(LL>=L&&RR<=R)
return seg[idx];
else if(LL>R||RR<L)
return{INT_MAX,INT_MAX};
return G1(query1(L,R,LL,(LL+RR)/2,idx*2+1),query1(L,R,(LL+RR)/2+1,RR,idx*2+2));
}
pair<int,int>query2(int L,int R,int LL=0,int RR=(1<<20)-1,int idx=0){
if(LL>=L&&RR<=R)
return seg2[idx];
else if(LL>R||RR<L)
return{INT_MAX,INT_MAX};
return G2(query2(L,R,LL,(LL+RR)/2,idx*2+1),query2(L,R,(LL+RR)/2+1,RR,idx*2+2));
}
void updA2(int v,int T,int LL=0,int RR=(1<<20)-1,int idx=0){
if(T==LL&&LL==RR){
SEG2[T].insert(-v);
seg2[idx]={-(*SEG2[T].begin()),T};
return;
}
if((LL+RR)/2>=T)
updA2(v,T,LL,(LL+RR)/2,idx*2+1);
else
updA2(v,T,(LL+RR)/2+1,RR,idx*2+2);
seg2[idx]=G2(seg2[idx*2+1],seg2[idx*2+2]);
}
void updR2(int v,int T,int LL=0,int RR=(1<<20)-1,int idx=0){
if(T==LL&&LL==RR){
SEG2[T].erase(-v);
if(SEG2[T].size())
seg2[idx]={-(*SEG2[T].begin()),T};
else
seg2[idx]={INT_MAX,INT_MAX};
return;
}
if((LL+RR)/2>=T)
updR2(v,T,LL,(LL+RR)/2,idx*2+1);
else
updR2(v,T,(LL+RR)/2+1,RR,idx*2+2);
seg2[idx]=G2(seg2[idx*2+1],seg2[idx*2+2]);
}
int main()
{
cin.tie(0),ios_base::sync_with_stdio(0);
cin>>N;
for(int i=0;i<(1<<21);i++){
seg[i]={INT_MAX,INT_MAX};
seg2[i]={INT_MAX,INT_MAX};
}
while(N--){
cin>>C>>L>>R;
if(C=='A'){
COUNT[make_pair(L,R)]++;
if(COUNT[make_pair(L,R)]==1){
updA1(L,R);
updA2(L,R);
pair<int,int>F1=query1(0,(1<<20)-1);
pair<int,int>F2=query2(0,(1<<20)-1);
if(F1.second>F2.first){
cout<<F2.second-F1.first<<endl;
continue;
}
F1=query1(R,(1<<20)-1);
F2=query2(0,L);
if(F1.first!=INT_MAX){
GLOBAL.insert({F1.second-L,L});
MP[make_pair(L,R)].insert({F1.first,F1.second});
MP[make_pair(F1.first,F1.second)].insert({L,R});
}
if(F2.first!=INT_MAX){
GLOBAL.insert({R-F2.first,F2.first});
MP[make_pair(L,R)].insert({F2.first,F2.second});
MP[make_pair(F2.first,F2.second)].insert({L,R});
}
}
else{
pair<int,int>F1=query1(0,(1<<20)-1);
pair<int,int>F2=query2(0,(1<<20)-1);
if(F1.second>F2.first){
cout<<F2.second-F1.first<<endl;
continue;
}
}
cout<<(GLOBAL.begin()->first)<<endl;
}
else{
COUNT[make_pair(L,R)]--;
if(COUNT[make_pair(L,R)]==0){
updR1(L,R);
updR2(L,R);
for(auto itr=MP[make_pair(L,R)].begin();itr!=MP[make_pair(L,R)].end();itr++){
MP[*itr].erase({L,R});
int L1=(itr->first),R1=(itr->second);
pair<int,int>F1=query1(R1,(1<<20)-1);
pair<int,int>F2=query2(0,L1);
if(F1.first!=INT_MAX){
if(MP[make_pair(L1,R1)].find({F1.first,F1.second})==MP[make_pair(L1,R1)].end()){
GLOBAL.insert({F1.second-L1,L1});
MP[make_pair(L1,R1)].insert({F1.first,F1.second});
MP[make_pair(F1.first,F1.second)].insert({L1,R1});
}
}
if(F2.first!=INT_MAX){
if(MP[make_pair(L1,R1)].find({F2.first,F2.second})==MP[make_pair(L1,R1)].end()){
GLOBAL.insert({R1-F2.first,F2.first});
MP[make_pair(L1,R1)].insert({F2.first,F2.second});
MP[make_pair(F2.first,F2.second)].insert({L1,R1});
}
}
int LL=min(L,L1),RR=max(R,R1);
GLOBAL.erase(GLOBAL.lower_bound(make_pair(RR-LL,LL)));
}
MP[make_pair(L,R)].clear();
pair<int,int>FF1=query1(0,(1<<20)-1);
pair<int,int>FF2=query2(0,(1<<20)-1);
if(FF1.second>FF2.first){
if(GLOBAL.size())exit(1);
cout<<FF2.second-FF1.first<<endl;
continue;
}
}
else{
pair<int,int>FF1=query1(0,(1<<20)-1);
pair<int,int>FF2=query2(0,(1<<20)-1);
if(FF1.second>FF2.first){
if(GLOBAL.size())exit(1);
cout<<FF2.second-FF1.first<<endl;
continue;
}
}
cout<<(GLOBAL.begin()->first)<<endl;
}
}
}
/*
5
A 1 2
A 5 6
A 3 4
R 1 2
R 5 6
*/

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