Submission #893796

#	Time	Username	Problem	Language	Result	Execution time	Memory
893796		danikoynov	Event Hopping 2 (JOI21_event2)	C++14	1 / 100	3082 ms	12912 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);
        else
        {
            pair < int, int > nw;
            nw.first = r + 1;
            nw.second = it -> second;
            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));
            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 {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 = len[0][fb.second];
    ///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;
    /**for (pair < int, int > cur : act)
        cout << cur.first << " ::: " << cur.second << endl;
    cout << "borders " << lb << " " << rb << " " << first_bef(lb) << " " << first_aft(rb) << endl;*/
    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]];
        }
    }

}
void create_sequence()
{
    act.insert({1, m});
    binary_lifting();
    vector < int > seq;
    for (int i = 1; i <= n && k > 0; i ++)
    {
        bool valid = true;
        for (int cur : seq)
        {
            if (intersect(seg[cur], seg[i]))
            {
                valid = false;
                break;
            }
        }

        if (!valid)
            continue;

        ///get_intersections(seg[i]);
        calc_pointers();
        int longest = get_longest(seg[i]);
        //cout << "longest " << i << " -- " << longest << endl;
        /*for (int j = 1; j <= m; j ++)
            cout << used[j] << " ";
        cout << endl;*/
        /*    for (int j = 1; j <= m; j ++)
        cout << len[0][j] << " ";
        cout << endl;*/
        if (longest >= k - 1)
        {

            seq.push_back(i);
            k --;
            remove_interval(lb_last, rb_last);
            get_intersections(seg[i]);
            apply_intersections();
        }

        /**for (int j = 1; j <= m; j ++)
            cout << used[j] << " ";
        cout << endl;*/
    }

    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()
{
    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


*/

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