Submission #312634

#	Time	Username	Problem	Language	Result	Execution time	Memory
312634		giorgikob	Interval Collection (CCO20_day2problem2)	C++14	25 / 25	3534 ms	284536 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;
        scanf("%c",&c);
        scanf("%c%d%d", &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){
            printf("%d ", (*b[x].begin() - *e[y].rbegin()) );
        } else {
            //cout << "second : ";
            printf("%d ", root->answer );
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |         scanf("%c",&c);
      |         ~~~~~^~~~~~~~~
Main.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |         scanf("%c%d%d", &c, &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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