Submission #312599

#	Time	Username	Problem	Language	Result	Execution time	Memory
312599		giorgikob	Interval Collection (CCO20_day2problem2)	C++14	0 / 25	2106 ms	418312 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{
    int answer = 1e9;
    int l = -1;
    int r = -1;
};

bla tree[2*N];

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(int node,int tl,int tr,int pos,int x,int y){

    if(tl == tr){
        go(x,y,tree[node].l,tree[node].r,tree[node].answer);
        //cout << tl << " --- " << tr << " : " << tree[node].l << " " << tree[node].r << endl;
        return ;
    }

    int mid = tl + tr; mid >>= 1;
    int left = node<<1; int right = left|1;

    if(pos <= mid){
        upd(left,tl,mid,pos,x,y);
    } else {
        upd(right,mid+1,tr,pos,x,y);
    }

    tree[node].l = mx(tree[left].l,tree[right].l);
    tree[node].r = mn(tree[left].r,tree[right].r);

    //cout << tl << " --- " << tr << " : " << tree[node].l << " and " << tree[node].r << endl;
    tree[node].answer = get(tree[right].r, tree[left].l);
    tree[node].answer = min(tree[node].answer, min(tree[left].answer, tree[right].answer));
}

int main(){
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

    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(1,1,N,l,-1,val); //cout << val << endl;

        if(e[r].size()) val = *e[r].rbegin(); else val = -2;
        upd(1,1,N,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 << tree[1].answer << endl;
        }
    }
}

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