oj.uz

Submission #893779

# Submission time Handle Problem Language Result Execution time Memory
893779 2023-12-27T12:08:54 Z danikoynov Event Hopping 2 (JOI21_event2) C++14
0 / 100
 3000 ms 13240 KB 
/**
 ____ ____ ____ ____ ____ ____
||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];

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

int first_bef(int pos)
{
    set < pair < int, int > > :: iterator it = act.lower_bound({pos, -1});
    if (it == act.begin())
        return 0;
    return min(pos - 1, prev(it) -> second);
}
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;
    if (it == act.end())
        return m + 1;
    return max(pos + 1, it -> first);
}


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;



    int longest = len[0][first_bef(lb)] + len[1][first_aft(rb)];
    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;
    }

    for (int i = 0; i <= m; i ++)
        dp[0][i] = pt[0][i];

    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 << 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 --;
            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 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8604 KB Output is correct
4 Execution timed out 3032 ms 13240 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8992 KB Output is correct
7 Correct 1 ms 8644 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Incorrect 1 ms 8540 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8992 KB Output is correct
7 Correct 1 ms 8644 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Incorrect 1 ms 8540 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8604 KB Output is correct
4 Execution timed out 3032 ms 13240 KB Time limit exceeded
5 Halted 0 ms 0 KB -