Submission #577194

#	Time	Username	Problem	Language	Result	Execution time	Memory
577194		dantoh000	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	136 ms	20432 KiB

event2

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> ii;
int n,k;
int l[100005];
int r[100005];
ii a[100005];
set<ii> s;
vector<int> ans;
int p[17][100005];
int st[17][100005];
int cur = 0;
int MX(int l, int r){
    if (l == r) return st[0][l];
    int d = 31-__builtin_clz(r-l+1);
    return max(st[d][l], st[d][r-(1<<d)+1]);
}

int find(int x){

    int lo = 1, hi = n;
    while (lo < hi){
        int mid = (lo+hi)/2;
        if (MX(1, mid) >= x){
            hi = mid;
        }
        else lo = mid+1;
    }
    return lo;
}
int query(int l, int r){

    int x = find(l);
    if (a[x].se > r) return 0;
    int ret = 1;
    for (int i = 16; i >= 0; i--){
        if (p[i][x] && a[p[i][x]].se <= r){
            x = p[i][x];

            ret += (1<<i);
        }
    }
    ///printf("querying %d %d --> %d\n",l,r, ret);
    return ret;
}

bool add(int l, int r){
    auto it = s.lower_bound({r, -1});
    assert(it != s.begin());
    auto LL = prev(it);
    auto RR = it;
    if (LL->se > l) return false;

    int L = LL->se;
    int R = RR->fi;
    int nw = cur - query(L, R) + query(L, l) + query(r, R) + 1;
    if (nw >= k){
        cur = nw;
        return true;
    }
    else return false;

}
int main(){
    scanf("%d%d",&n,&k);
    for (int i = 1; i <= n; i++){
        scanf("%d%d",&l[i], &r[i]);
        a[i] = {l[i], r[i]};
    }
    sort(a+1, a+n+1, [](ii a, ii b){
            return a.se < b.se;
    });

    for (int i = 1; i <= n; i++){
        st[0][i] = a[i].fi;
    }
    for (int k = 1; k < 17; k++){
        for (int i = 1; i <= n; i++){
            if (i + (1<<(k-1)) <= n){
                st[k][i] = max(st[k-1][i], st[k-1][i+(1<<(k-1))]);
            }
        }
    }
    memset(p, 0, sizeof(p));
    for (int i = 1; i <= n; i++){
        p[0][i] = find(a[i].se);
        if (a[p[0][i]].fi < a[i].se) p[0][i] = 0;
    }
    for (int k = 1; k < 17; k++){
        for (int i = 1; i <= n; i++){
            if (p[k-1][i]) p[k][i] = p[k-1][p[k-1][i]];
        }
    }
    s.insert({0,0});
    s.insert({1000000001,1000000001});
    cur = query(1, 1000000000);
    if (cur < k){
        printf("-1\n");
        return 0;
    }
    for (int i = 1; i <= n; i++){
        if (add(l[i], r[i])){
            ans.push_back(i);
            s.insert({l[i], r[i]});
        }
    }
    for (int i = 0; i < k; i++) printf("%d\n",ans[i]);




}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
event2.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%d%d",&l[i], &r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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