Submission #314124

#	Time	Username	Problem	Language	Result	Execution time	Memory
314124		demetre	Interval Collection (CCO20_day2problem2)	C++14	25 / 25	4271 ms	292236 KiB

Main

# include <bits/stdc++.h>

using namespace std;

pair <pair <long long, long long> , long long>  tree[4000035];
long long  x,le,ri,l1,r1,ans,q,mnr,mxl;
long long mx=1000005;

char ch;

multiset<long long>::iterator it;
multiset<long long> l,r,ms1[1000005],ms2[1000005];

void update(long long n, long long l, long long r, long long ind, long long val, int ty){
    
    if (l>ind || r<ind) return;
    if (l==r){
        if (ty==0)
            tree[n].first.second=val;
            
        else 
			tree[n].first.first=val;
			
        tree[n].second=tree[n].first.second-tree[n].first.first;
        return;
    }
    long long mid=(l+r)/2;
    
    update(2*n, l, mid, ind, val, ty);
    update(2*n+1, mid+1, r, ind, val, ty);
    
    tree[n].first.second=min(tree[2*n].first.second, tree[2*n+1].first.second);
    tree[n].first.first=max(tree[2*n].first.first, tree[2*n+1].first.first);
    
    x=min(tree[2*n].second, tree[2*n+1].second);
    
    tree[n].second=min(x,tree[2*n+1].first.second-tree[2*n].first.first);
}

int main(){
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    
    cin>>q;
    for (long long i=1; i<=4000020; i++)
    {
        tree[i].first.second=1000000000;
        tree[i].first.first=-1000000000;
        tree[i].second=2000000000;
    }
    for (int i=q; i>0; i--){
        cin >> ch;
        cin >> le >> ri;
        if (ch=='R'){
            l.erase(l.find(le));
            r.erase(r.find(ri));
            
            ms1[le].erase(ms1[le].find(ri));
            ms2[ri].erase(ms2[ri].find(le));
            
            if (!ms1[le].size()) ms1[le].insert(1e9);
            if (!ms2[ri].size()) ms2[ri].insert(-1e9);
            
            mnr=*ms1[le].begin();
            update(1,1,mx,le,mnr,0);
            	it=ms2[ri].end();
                it--;
            mxl=*it;
            update(1,1,mx,ri,mxl,1);
        }
        else{
            ms1[le].insert(ri);
            ms2[ri].insert(le);
            l.insert(le);
            r.insert(ri);
            mnr=*ms1[le].begin();
            it=ms2[ri].end();
            it--;
            mxl=*it;
            update(1,1,mx,le,mnr,0);
            update(1,1,mx,ri,mxl,1);
        }
        
      	it=l.end();
       	it--;
       	
        mxl=*it;
        mnr=*(r.begin());
        
        if (mnr<=mxl)
            cout<<tree[1].second<<endl;
        
        
        else{
            r1=*(ms1[mxl].begin());
            it=ms2[mnr].end();
            it--;
            l1=*it;
            
            cout << r1-l1 << endl;
        }
    }
}

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