Submission #267075

#	Time	Username	Problem	Language	Result	Execution time	Memory
267075		ChrisT	Interval Collection (CCO20_day2problem2)	C++17	25 / 25	4700 ms	218816 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct node
{
    int maxl, minr, ans;
};

vector<node> seg;
vector<multiset<int>> lp, rp;
multiset<pair<int, int>> byl, byr;

node combine(node a, node b)
{
    node c;
    c.maxl=max(a.maxl, b.maxl);
    c.minr=min(a.minr, b.minr);
    c.ans=min(a.ans, b.ans);
    if(b.minr!=0x3f3f3f3f && a.maxl!=-0x3f3f3f3f)
        c.ans=min(c.ans, b.minr-a.maxl);
    return c;
}

void build(int idx, int begin, int end)
{
    if(begin==end)
        seg[idx].maxl=-0x3f3f3f3f, seg[idx].minr=0x3f3f3f3f, seg[idx].ans=0x3f3f3f3f;
    else
    {
        int mid=(begin+end)/2;
        build(idx*2, begin, mid);
        build(idx*2+1, mid+1, end);
        seg[idx]=combine(seg[idx*2], seg[idx*2+1]);
    }
}

void update(int idx, int begin, int end, int x, node v)
{
    if(x<begin || end<x)
        return;
    if(begin==end)
        seg[idx]=v;
    else
    {
        int mid=(begin+end)/2;
        update(idx*2, begin, mid, x, v);
        update(idx*2+1, mid+1, end, x, v);
        seg[idx]=combine(seg[idx*2], seg[idx*2+1]);
    }
}

void recalc(int x)
{
    node n;
    if(lp[x].empty())
        n.maxl=-0x3f3f3f3f;
    else
        n.maxl=*lp[x].rbegin();
    if(rp[x].empty())
        n.minr=0x3f3f3f3f;
    else
        n.minr=*rp[x].begin();
    if(n.minr!=0x3f3f3f3f && n.maxl!=-0x3f3f3f3f)
        n.ans=n.minr-n.maxl;
    else
        n.ans=0x3f3f3f3f;
    update(1, 1, seg.size()/2, x, n);
}

int get_ans()
{
    if(seg[1].ans>=0x3f3f3f3f)
    {
        int r=-byl.rbegin()->second;
        int l=-byr.begin()->second;
        return r-l;
    }
    return seg[1].ans;
}

void init(int n)
{
    int lg=0;
    while((1<<lg)<n)
        lg++;
    seg.resize(1<<(lg+1));
    lp.resize(n+1);
    rp.resize(n+1);
    build(1, 1, 1<<lg);
}

int add_interval(int l, int r)
{
    byl.insert({l, -r});
    byr.insert({r, -l});
    lp[r].insert(l);
    rp[l].insert(r);
    recalc(l);
    recalc(r);
    return get_ans();
}

int remove_interval(int l, int r)
{
    byl.erase(byl.find({l, -r}));
    byr.erase(byr.find({r, -l}));
    lp[r].erase(lp[r].find(l));
    rp[l].erase(rp[l].find(r));
    recalc(l);
    recalc(r);
    return get_ans();
}

int main()
{
    int n, q;
    scanf("%d", &q);
    n = 1000000;
    init(n);
    for(int i=0; i<q; i++)
    {
        char t;
        int l, r;
        scanf(" %c%d%d", &t, &l, &r);
        if(t=='A')
            printf("%d\n", add_interval(l, r));
        else
            printf("%d\n", remove_interval(l, r));
    }
    return 0;
}

Compilation message (stderr)

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

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