Submission #386808

#	Time	Username	Problem	Language	Result	Execution time	Memory
386808		BartolM	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	236 ms	17760 KiB

event2

#define DEBUG 0
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=1e5+5;
const int LOG=18;

int n, m, k;
ppi p[N];
pii poc[N];
vector <pii> v;
int nx[LOG][N];
vector <int> res;
set <pii> S;
vector <int> sol;

void build() {
    for (int i=1; i<LOG; ++i) {
        for (int j=0; j<=m; ++j) {
            nx[i][j]=nx[i-1][nx[i-1][j]];
        }
    }
}

int calc(pii pp, int gr) {
    if (pp.Y>gr) return -INF;
    int x=lower_bound(v.begin(), v.end(), mp(pp.Y, -1))-v.begin();
    if (v[x].Y>gr) return 1;
    int ret=2;
    for (int i=LOG-1; i>=0; --i) {
        if (v[nx[i][x]].Y<=gr) {
            ret+=(1<<i);
            x=nx[i][x];
        }
    }
    return ret;
}

int cmp(ppi a, ppi b) {
    if (a.X.X==b.X.X) return a.X.Y>b.X.Y;
    return a.X.X<b.X.X;
}

void solve() {
    sort(p, p+n, cmp);
    int rig=INF;
    for (int i=n-1; i>=0; --i) {
        if (p[i].X.Y<rig) {
            rig=p[i].X.Y;
            v.pb(p[i].X);
        }
    }
    reverse(v.begin(), v.end());

    #if DEBUG
        printf("----------------\n");
        for (pii pp:v) printf("%d %d\n", pp.X, pp.Y);
    #endif // DEBUG

    m=v.size();
    v.pb(mp(INF, INF+1));
    nx[0][m]=m;
    for (int i=0; i<m; ++i) nx[0][i]=lower_bound(v.begin(), v.end(), mp(v[i].Y, -1))-v.begin();
    build();

    S.insert(mp(-2, -1));
    S.insert(mp(INF, INF+1));

    int uk=calc(mp(-2, -1), INF);
    if (uk<=k) {
        printf("-1\n");
        return;
    }

    for (int i=0; i<n; ++i) {
        if ((int)sol.size()>=k) break;
        pii pp=poc[i];
        if (S.count(pp)) continue;
        auto it=S.insert(pp).X;
        auto pr=it, slj=it;
        pr--; slj++;

        int prije=calc((*pr), slj->X);
        int sad=calc((*pr), it->X)+calc(pp, slj->X);
#if DEBUG
        printf("pp: (%d, %d), prije: %d, sad: %d\n", pp.X, pp.Y, prije, sad);
#endif
        if (uk-prije+sad<=k) S.erase(it);
        else {
            sol.pb(i+1);
            uk+=sad-prije;
        }
    }
    for (int x:sol) printf("%d\n", x);
}

void load() {
    scanf("%d %d", &n, &k);
    for (int i=0; i<n; ++i) {
        scanf("%d %d", &p[i].X.X, &p[i].X.Y);
        p[i].Y=i;
        poc[i]=p[i].X;
    }
}

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

/*
5
6 11
2 4
1 5
4 10
4 6
*/

Compilation message (stderr)

event2.cpp: In function 'void load()':
event2.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
event2.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |         scanf("%d %d", &p[i].X.X, &p[i].X.Y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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