Submission #486701

#	Time	Username	Problem	Language	Result	Execution time	Memory
486701		alextodoran	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	615 ms	29112 KiB

event2

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;

const int BITS = 17;

int N, K;

struct Segment
{
    int l, r;
};

bool operator < (const Segment &a, const Segment &b)
{
    if(a.l != b.l)
        return a.l < b.l;
    return a.r > b.r;
}

Segment seg[N_MAX + 2];

vector <Segment> sorted;

int anc[N_MAX + 2][BITS];

int sumMax;

set <int> del;
set <pair <int, int>> activeR;
set <pair <int, int>> activeL;

int getMax (int first, int last)
{
    if(first > last)
        return 0;
    int curr = last;
    int cnt = 1;
    for(int bit = BITS - 1; bit >= 0; bit--)
        if(first <= anc[curr][bit])
        {
            cnt += (1 << bit);
            curr = anc[curr][bit];
        }
    return cnt;
}

void init ()
{
    int j = -1;
    for(int i = 0; i < (int) sorted.size(); i++)
    {
        while(j < i - 1 && sorted[j + 1].r < sorted[i].l)
            j++;
        anc[i][0] = j;
    }

    for(int bit = 1; bit < BITS; bit++)
        for(int i = 0; i < (int) sorted.size(); i++)
        {
            if(anc[i][bit - 1] == -1)
                anc[i][bit] = -1;
            else
                anc[i][bit] = anc[anc[i][bit - 1]][bit - 1];
        }

    for(int i = 0; i < (int) sorted.size(); i++)
    {
        activeL.insert(make_pair(sorted[i].l, i));
        activeR.insert(make_pair(sorted[i].r, i));
    }
    del.insert(-1);
    del.insert((int) sorted.size());

    sumMax = getMax(0, (int) sorted.size() - 1);
}

int cnt[N_MAX + 2];

void delSeg (int i)
{
    cnt[i]++;
    if(del.find(i) != del.end())
        return;

    set <int> :: iterator itr = del.upper_bound(i);
    set <int> :: iterator itl = prev(itr);

    int il = *itl;
    int ir = *itr;

    sumMax -= getMax(il + 1, ir - 1);
    del.insert(i);
    activeL.erase(make_pair(sorted[i].l, i));
    activeR.erase(make_pair(sorted[i].r, i));
    sumMax += getMax(il + 1, i - 1);
    sumMax += getMax(i + 1, ir - 1);
}
void addSeg (int i)
{
    cnt[i]++;
    set <int> :: iterator it = del.find(i);
    if(it == del.end())
        return;

    set <int> :: iterator itr = next(it);
    set <int> :: iterator itl = prev(it);

    int il = *itl;
    int ir = *itr;

    sumMax -= getMax(il + 1, i - 1);
    sumMax -= getMax(i + 1, ir - 1);
    del.erase(it);
    activeL.insert(make_pair(sorted[i].l, i));
    activeR.insert(make_pair(sorted[i].r, i));
    sumMax += getMax(il + 1, ir - 1);
}

void delAll (int l, int r)
{
    set <pair <int, int>> :: iterator itl = activeR.upper_bound(make_pair(l, -1));
    set <pair <int, int>> :: iterator itr = activeL.upper_bound(make_pair(r, INT_MAX));
    if(itl == activeR.end())
        return;
    if(itr == activeL.begin())
        return;
    itr = prev(itr);
    int L = itl->second;
    int R = itr->second;
    for(int i = L; i <= R; i++)
        delSeg(i);
}

int delTest (int l, int r)
{
    set <pair <int, int>> :: iterator itl = activeR.upper_bound(make_pair(l, -1));
    set <pair <int, int>> :: iterator itr = activeL.upper_bound(make_pair(r, INT_MAX));
    if(itl == activeR.end())
        return sumMax;
    if(itr == activeL.begin())
        return sumMax;
    itr = prev(itr);
    int L = itl->second;
    int R = itr->second;
    if(L > R)
        return sumMax;
    delSeg(L);
    delSeg(R);
    int res = sumMax - getMax(L + 1, R - 1);
    addSeg(L);
    addSeg(R);
    return res;
}

struct SGTNode
{
    ll sum;
    int lazy;
};

SGTNode operator + (const SGTNode &u, const SGTNode &v)
{
    return SGTNode{u.sum + v.sum, 0};
}

SGTNode SGT[N_MAX * 2 * 4 + 2];

void split (int node, int l, int r)
{
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    SGT[lSon].sum += (ll) SGT[node].lazy * (mid - l + 1);
    SGT[rSon].sum += (ll) SGT[node].lazy * (r - mid);
    SGT[lSon].lazy += SGT[node].lazy;
    SGT[rSon].lazy += SGT[node].lazy;
    SGT[node].lazy = 0;
}

void update (int node, int l, int r, int ul, int ur, int uval)
{
    if(ul <= l && r <= ur)
    {
        SGT[node].sum += (ll) uval * (r - l + 1);
        SGT[node].lazy += uval;
        return;
    }

    split(node, l, r);

    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    if(ul <= mid)
        update(lSon, l, mid, ul, ur, uval);
    if(mid + 1 <= ur)
        update(rSon, mid + 1, r, ul, ur, uval);

    SGT[node] = SGT[lSon] + SGT[rSon];
}
void update (int ul, int ur, int uval)
{
    update(1, 1, N * 2, ul, ur, uval);
}

ll query (int node, int l, int r, int ql, int qr)
{
    if(ql <= l && r <= qr)
        return SGT[node].sum;

    split(node, l, r);

    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;

    ll sum = 0;
    if(ql <= mid)
        sum += query(lSon, l, mid, ql, qr);
    if(mid + 1 <= qr)
        sum += query(rSon, mid + 1, r, ql, qr);
    return sum;
}
ll query (int ql, int qr)
{
    return query(1, 1, N * 2, ql, qr);
}

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

    cin >> N >> K;
    for(int i = 1; i <= N; i++)
    {
        cin >> seg[i].l >> seg[i].r;
    }

    {
        vector <int> aux;
        for(int i = 1; i <= N; i++)
        {
            aux.push_back(seg[i].l);
            aux.push_back(seg[i].r);
        }
        sort(aux.begin(), aux.end());
        aux.resize(unique(aux.begin(), aux.end()) - aux.begin());

        unordered_map <int, int> mp;
        for(int i = 0; i < (int) aux.size(); i++)
            mp[aux[i]] = i + 1;

        for(int i = 1; i <= N; i++)
        {
            seg[i].l = mp[seg[i].l];
            seg[i].r = mp[seg[i].r];
        }
    }

    for(int i = 1; i <= N; i++)
        seg[i].r--;

    {
        for(int i = 1; i <= N; i++)
            sorted.push_back(seg[i]);
        sort(sorted.begin(), sorted.end());

        vector <Segment> newSorted;
        for(Segment s : sorted)
        {
            while(newSorted.empty() == false && s.r <= newSorted.back().r)
                newSorted.pop_back();
            newSorted.push_back(s);
        }
        sorted = newSorted;
    }

    init();

    if(sumMax < K)
    {
        cout << "-1\n";
        return 0;
    }

    int curr = 1;
    for(int i = 1; i <= K; i++)
    {
        while(curr <= N)
        {
            if(query(seg[curr].l, seg[curr].r) > 0)
            {
                curr++;
                continue;
            }
            update(seg[curr].l, seg[curr].r, + 1);
            if(delTest(seg[curr].l, seg[curr].r) < K - i)
            {
                update(seg[curr].l, seg[curr].r, - 1);
                curr++;
                continue;
            }
            delAll(seg[curr].l, seg[curr].r);
            break;
        }
        cout << curr << "\n";
        curr++;
    }

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 61 / 61