Submission #893700

#	Time	Username	Problem	Language	Result	Execution time	Memory
893700		danikoynov	Event Hopping 2 (JOI21_event2)	C++14	32 / 100	3081 ms	3680 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;

}

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 longest = len[0][lb] + len[1][rb];
    //cout << "borderes " << lb << " " << 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 create_sequence()
{
    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 << i << " -- " << longest << endl;
        for (int j = 1; j <= m; j ++)
            cout << pt[1][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 --;
            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 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: 0 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 0 / 61