Submission #486662

#	Time	Username	Problem	Language	Result	Execution time	Memory
486662		alextodoran	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	3100 ms	11344 KiB

event2

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

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;

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 mars[N_MAX * 2 + 2];
int pref[N_MAX * 2 + 2];

void update (Segment s, int val)
{
    mars[s.l] += val;
    mars[s.r + 1] -= val;
}
void init ()
{
    for(int i = 1; i <= N * 2; i++)
        pref[i] = pref[i - 1] + mars[i];

    for(int i = 1; i <= N * 2; i++)
        pref[i] = pref[i - 1] + pref[i];
}

bool check (Segment s)
{
    return (pref[s.r] - pref[s.l - 1] == 0);
}

int dp[N_MAX + 2];

int getMax ()
{
    dp[0] = (check(sorted[0]) == true ? 1 : 0);
    for(int i = 1; i < (int) sorted.size(); i++)
    {
        dp[i] = dp[i - 1];
        if(check(sorted[i]) == true)
        {
            int l = -1, r = i - 1;
            while(l < r)
            {
                int mid = (l + r + 1) / 2;
                if(sorted[mid].r < sorted[i].l)
                    l = mid;
                else
                    r = mid - 1;
            }
            if(l != -1)
                dp[i] = max(dp[i], dp[l] + 1);
        }
    }
    return dp[(int) sorted.size() - 1];
}

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)
        {
            if(newSorted.empty() || s.r > newSorted.back().r)
                newSorted.push_back(s);
        }
        sorted = newSorted;
    }

    vector <int> answer;

    int curr = 1;
    for(int i = 1; i <= K; i++)
    {
        while(curr <= N)
        {
            if(check(seg[curr]) == false)
            {
                curr++;
                continue;
            }
            update(seg[curr], + 1);
            init();
            if(getMax() < K - i)
            {
                update(seg[curr], - 1);
                init();
                curr++;
                continue;
            }
            break;
        }
        if(curr > N)
        {
            cout << "-1\n";
            return 0;
        }
        answer.push_back(curr);
        curr++;
    }

    for(int i : answer)
        cout << i << "\n";

    return 0;
}

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