Submission #986281

#	Time	Username	Problem	Language	Result	Execution time	Memory
986281		alexdd	Interval Collection (CCO20_day2problem2)	C++17	25 / 25	3230 ms	307136 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9;
const int maxv = 1000010;
struct node
{
    int rez;
    int tole,tori;
};
node combine(node x, node y)
{
    node aux;
    aux.rez = min(min(x.rez,y.rez),x.tole+y.tori);
    aux.tori = min(y.tori, x.tori);
    aux.tole = min(x.tole, y.tole);
    return aux;
}
node aint[2100000];
void build(int nod, int st, int dr)
{
    aint[nod].rez = aint[nod].tole = aint[nod].tori = INF;
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
}
void upd(int nod, int st, int dr, int poz, int tip, int newv)
{
    if(st==dr)
    {
        if(tip==0)
        {
            aint[nod].tori = newv;
        }
        else
        {
            aint[nod].tole = -newv;
        }
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij) upd(nod*2,st,mij,poz,tip,newv);
    else upd(nod*2+1,mij+1,dr,poz,tip,newv);
    aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
}

set<pair<int,int>> sle[1000005],sri[1000005];
set<pair<int,int>> caple,capri,slun;
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int t;
    cin>>t;
    char tip;
    int le,ri;
    build(1,0,maxv);
    while(t--)
    {
        cin>>tip>>le>>ri;
        le++;ri++;
        upd(1,0,maxv,ri-1,1,-INF);
        upd(1,0,maxv,le,0,INF);
        if(tip=='A')
        {
            sle[ri].insert({le,t});
            sri[le].insert({ri,t});
            caple.insert({le,t});
            capri.insert({ri,t});
            slun.insert({ri-le,t});
        }
        else
        {
            sle[ri].erase(sle[ri].lower_bound({le,0}));
            sri[le].erase(sri[le].lower_bound({ri,0}));
            caple.erase(caple.lower_bound({le,0}));
            capri.erase(capri.lower_bound({ri,0}));
            slun.erase(slun.lower_bound({ri-le,0}));
        }
        if(!sle[ri].empty()) upd(1,0,maxv,ri-1,1,(*prev(sle[ri].end())).first);
        if(!sri[le].empty()) upd(1,0,maxv,le,0,(*sri[le].begin()).first);

        int maxle = (*prev(caple.end())).first;
        int minri = (*capri.begin()).first;

        if(maxle>=minri)
        {
            cout<<aint[1].rez<<"\n";
        }
        else
        {
            int cv=0;
            cv += (*sri[maxle].begin()).first;
            cv -= (*prev(sle[minri].end())).first;
            cout<<cv<<"\n";
        }
    }
    return 0;
}
/**
5
A 1 5
A 2 7
A 4 6
A 6 8
R 4 6
*/

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