Submission #893810

#	Time	Username	Problem	Language	Result	Execution time	Memory
893810		danikoynov	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	248 ms	20424 KiB

event2

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10;

struct interval
{
    int l, r;
};

int n, k;
interval seg[maxn];
void input()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++)
        cin >> seg[i].l >> seg[i].r;
}


bool cmp(interval it1, interval it2)
{
    if (it1.l != it2.l)
        return it1.l < it2.l;
    return it1.r > it2.r;
}

interval rel[maxn];
int m;
void get_relevant()
{
    vector < interval > vec;
    for (int i = 1; i <= n; i ++)
        vec.push_back(seg[i]);

    sort(vec.begin(), vec.end(), cmp);
    int cl = 1e9 + 10;
    for (int i = n - 1; i >= 0; i --)
    {
        if (vec[i].r >= cl)
        {
            continue;
        }
        rel[++ m] = vec[i];
        cl = vec[i].r;
    }

    reverse(rel + 1, rel + m + 1);
}

int len[2][maxn], pt[2][maxn], used[maxn];

void calc_pointers()
{
    int last = 0;
    rel[m + 1].l = 1e9 + 10;
    for (int i = 1; i <= m; i ++)
    {
        if (used[i])
            continue;
        len[0][i] = 0;
        pt[0][i] = 0;
        if (last != 0)
            pt[0][i] = pt[0][last];
        while(rel[pt[0][i]].r <= rel[i].l)
            pt[0][i] ++;
        pt[0][i] --;
        while(pt[0][i] > 0 && used[pt[0][i]])
            pt[0][i] --;

        len[0][i] = len[0][pt[0][i]] + 1;
        last = i;
    }

    last = m + 1;
    for (int i = m; i > 0; i --)
    {
        if (used[i])
            continue;
        len[1][i] = 0;
        pt[1][i] = m + 1;
        if (last != m + 1)
            pt[1][i] = pt[1][last];
        while(rel[pt[1][i]].l >= rel[i].r)
            pt[1][i] --;
        pt[1][i] ++;
        while(pt[1][i] <= m && used[pt[1][i]])
            pt[1][i] ++;
        len[1][i] = len[1][pt[1][i]] + 1;
        ///cout << "line 107 " << i << " " << pt[1][i] << endl;
        last = i;
    }
}

bool intersect(interval a, interval b)
{
    if (a.l == b.l)
        return true;
    if (a.l > b.l)
        swap(a, b);
    if (a.r >= b.r)
        return true;
    return a.r > b.l;
}

void get_intersections(interval cur)
{
    for (int i = 1; i <= m; i ++)
        if (used[i] == 0 && intersect(rel[i], cur))
            used[i] = 2;

}
set < pair < int, int > > act;
const int maxlog = 21;

int dp[maxlog][maxn];

int fen[2][maxn];

void add(int r, int p, int v)
{
    ///cout << v << endl;
    for (int i = p; i <= m; i += (i & -i))
        fen[r][i] += v;
}

int sum(int r, int p)
{
    int s = 0;
    for (int i = p; i > 0; i -= (i & -i))
        s += fen[r][i];
    return s;
}


int get_length(int pos, int to)
{
    int jump = 0;
    for (int bit = maxlog - 1; bit >= 0; bit --)
    {
        //cout << "get length " << pos << " " << jump << " " << m << endl;
        if (dp[bit][pos] <= to)
        {
            jump += (1 << bit);
            pos = dp[bit][pos];
        }
    }
    return jump + 1;
}

int get_pos(int r, int pos)
{
    return sum(r, pos) - sum(r, pos - 1);
}

void remove_interval(int l, int r)
{
    while(true)
    {
        set < pair < int, int > > :: iterator it = act.lower_bound({l, -1});
        if (it == act.end() || it -> first > r)
            break;
        if (it -> second <= r)
        {
            act.erase(it);
            add(1, it -> first, -get_length(it -> first, it -> second));
        }
        else
        {
            pair < int, int > nw;
            nw.first = r + 1;
            nw.second = it -> second;
            act.erase(it);
            add(1, it -> first, -get_length(it -> first, it -> second));
            act.insert(nw);
            add(1, nw.first, get_length(nw.first, nw.second));
            break;
        }
    }
    set < pair < int, int > > :: iterator it = act.lower_bound({l, -1});
    //cout << "cur " << it -> first << " " << it -> second << endl;
    if (it != act.begin())
    {
        it = prev(it);
        ///cout << "back " << it -> first << " " << it -> second << endl;
        if (it -> second > r)
        {
            pair < int, int > lf = *it, rf = *it;
            lf.second = l - 1;
            rf.first = r + 1;
            act.erase(it);
            add(1, it -> first, -get_pos(1,it -> first));
            act.insert(lf);
            add(1, lf.first, get_length(lf.first, lf.second));
            act.insert(rf);
            add(1, rf.first, get_length(rf.first, rf.second));
        }
        else if (it -> second >= l)
        {
            pair < int, int > nw = *it;
            nw.second = l - 1;
            act.erase(it);
            add(1, it -> first, -get_pos(1, it -> first));
            act.insert(nw);
            add(1, nw.first, get_length(nw.first, nw.second));
        }
    }
}

pair < int, int > first_bef(int pos)
{
    set < pair < int, int > > :: iterator it = act.lower_bound({pos, -1});
    if (it == act.begin())
        return {0, 0};
    return {prev(it) -> first, min(pos - 1, prev(it) -> second)};
}
pair < int, int > first_aft(int pos)
{

    set < pair < int, int > > :: iterator it = act.lower_bound({pos, -1});
    if (it != act.begin() && prev(it) -> second > pos)
        return {pos + 1, prev(it) -> second};
    if (it == act.end())
        return {m + 1, m + 1};
    return {max(pos + 1, it -> first), it -> second};
}


int lb_last, rb_last;
int get_longest(interval cur)
{
    /**int lb = 1;
    while(lb <= m && rel[lb].r <= cur.l)
        lb ++;
    lb --;
    while(lb > 0 && used[lb])
        lb --;

    int rb = m;
    while(rb > 0 && rel[rb].l >= cur.r)
        rb --;
    rb ++;
    while(rb <= m && used[rb])
        rb ++;*/

    int lf = 1, rf = m;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (rel[mf].r <= cur.l)
            lf = mf + 1;
        else
            rf = mf - 1;
    }

    int lb = lf;

    lf = 1;
    rf = m;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (rel[mf].l >= cur.r)
            rf = mf - 1;
        else
            lf = mf + 1;
    }

    int rb = rf;


    pair < int, int > fb = first_bef(lb);
    pair < int, int > fa = first_aft(rb);
    ///cout << sum(1, m) << " :::: " << sum(1, fa.second) << endl;
    int longest = 0;
    if (fb.first != 0)
        longest += get_length(fb.first, fb.second) + sum(1, fb.first - 1);

    ///cout << "HERE " << fa.first << " " << fa.second << " " << get_length(fa.first, fa.second) << endl;
    if (fa.second != m + 1)
        longest += get_length(fa.first, fa.second) + sum(1, m) - sum(1, fa.second);
    ///int longest = len[0][fb.second] + len[1][fa.first];
    lb_last = lb;
    rb_last = rb;

    return longest;
}

void reverse_intersections()
{
    for (int i = 1; i <= m; i ++)
        if (used[i] == 2)
            used[i] = 0;
}

void apply_intersections()
{
    for (int i = 1; i <= m; i ++)
        if (used[i] == 2)
            used[i] = 1;
}


void binary_lifting()
{
    int last = 0;
    rel[m + 1].l = 1e9 + 10;
    for (int i = 1; i <= m; i ++)
    {
        if (used[i])
            continue;
        len[0][i] = 0;
        pt[0][i] = 0;
        if (last != 0)
            pt[0][i] = pt[0][last];
        while(rel[pt[0][i]].r <= rel[i].l)
            pt[0][i] ++;
        pt[0][i] --;
        while(pt[0][i] > 0 && used[pt[0][i]])
            pt[0][i] --;

        len[0][i] = len[0][pt[0][i]] + 1;
        last = i;
    }

    last = m + 1;
    for (int i = m; i > 0; i --)
    {
        if (used[i])
            continue;
        len[1][i] = 0;
        pt[1][i] = m + 1;
        if (last != m + 1)
            pt[1][i] = pt[1][last];
        while(rel[pt[1][i]].l >= rel[i].r)
            pt[1][i] --;
        pt[1][i] ++;
        while(pt[1][i] <= m && used[pt[1][i]])
            pt[1][i] ++;
        len[1][i] = len[1][pt[1][i]] + 1;
        ///cout << "line 107 " << i << " " << pt[1][i] << endl;
        last = i;
    }

    for (int i = 0; i <= m; i ++)
        dp[0][i] = pt[1][i];
    for (int j = 0; j < maxlog; j ++)
        dp[j][m + 1] = m + 1;
    for (int j = 1; j < maxlog; j ++)
    {
        for (int i = 1; i <= m; i ++)
        {
            dp[j][i] = dp[j - 1][dp[j - 1][i]];
        }
    }

}

set < pair < int, int > > ranges;

bool match(interval cur)
{
    set < pair < int, int > > :: iterator it = ranges.lower_bound({cur.l, -1});
    if (it != ranges.end() && it -> first < cur.r)
        return true;
    if (it != ranges.begin())
    {
        it = prev(it);
        if (it -> second > cur.l)
        {
            //cout << cur.l << " : " << cur.r << " " << it -> second << endl;
            return true;
        }
    }
    return false;
}
void create_sequence()
{
    act.insert({1, m});
    binary_lifting();
    add(1, 1, get_length(1, m));
    vector < int > seq;
    for (int i = 1; i <= n && k > 0; i ++)
    {
        if (match(seg[i]))
            continue;
        int longest = get_longest(seg[i]);

        if (longest >= k - 1)
        {

            seq.push_back(i);
            k --;
            remove_interval(lb_last, rb_last);
            ranges.insert({seg[i].l, seg[i].r});
        }

    }

    if (k != 0)
    {
        cout << -1 << endl;
        return;
    }
    for (int cur : seq)
        cout << cur << endl;
}
void solve()
{
    input();
    get_relevant();
    ///calc_pointers();
    create_sequence();
}

int main()
{
    speed();
    solve();
    return 0;
}

/**
2 2
1 3
1 2

20 9
18 22
2 5
28 31
21 25
25 27
3 6
36 39
22 26
8 12
27 31
27 29
32 36
14 18
16 20
22 26
10 14
17 21
13 17
15 19
37 40

20 5
715591101 817706977
777008847 930020190
379125190 717746290
308826535 651449374
799848635 899870053
173402733 393191194
565584335 789226348
291163241 758381981
249473019 374801668
294956234 880404922
451362750 913870571
98855617 246302398
339866606 382702111
293058132 409201146
478015003 708631705
377970105 957002219
588778390 752946205
265885640 799122807
848738346 862888689
216577014 930520748


*/

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