Submission #312632

#	Time	Username	Problem	Language	Result	Execution time	Memory
312632		giorgikob	Interval Collection (CCO20_day2problem2)	C++14	25 / 25	4626 ms	290896 KiB

Main

#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 = -1e9;
    int r = 1e9;
};


multiset<int>b[N],e[N],L,R;


inline void upd(bla* &node,int tl,int tr,int pos,bool ok){

    if(tl == tr){
        if(!ok){
            if(e[tl].size()){
                node->l = *e[tl].rbegin();
            } else {
                node->l = -1e9;
            }
        } else {
            if(b[tr].size()){
                node->r = *b[tr].begin();
            } else {
                node->r = 1e9;
            }
        }
        node->answer = node->r - node->l;
        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,ok);
    } else {
        upd(node->right,mid+1,tr,pos,ok);
    }

    node->l = max(node->left->l,node->right->l);
    node->r = min(node->left->r,node->right->r);

    node->answer = 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));
        }


        upd(root,1,N-1,l,1);
        upd(root,1,N-1,r,0);

        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;
        }
    }
}

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