Submission #312625

#	Time	Username	Problem	Language	Result	Execution time	Memory
312625		giorgikob	Interval Collection (CCO20_day2problem2)	C++14	7 / 25	2660 ms	291148 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 = -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);
    }
    if(x == -2 || y == -2){
        answer = 1e9;
        return ;
    }
    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;
        }
    }
}

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