Submission #577172

#	Time	Username	Problem	Language	Result	Execution time	Memory
577172		dantoh000	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	107 ms	19352 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];
    ///printf("mx %d %d\n",l,r);
    int d = 31-__builtin_clz(r-l+1);
    ///printf("d %d\n",d);
    return max(st[d][l], st[d][r-(1<<d)+1]);
}

int find(int x){

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

    int x = find(l);
    int ret = 0;
    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){
    ///printf("can add %d %d?\n",l,r);
    auto it = s.lower_bound({r, -1});
    auto LL = prev(it);
    auto RR = it;
    ///printf("%d %d\n",LL->fi, LL->se);
    if (LL->se >= l) return false;

    int L = LL->se;
    int R = RR->fi;
    ///printf("surrounding %d %d\n",L,R);
    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))]);
            }
        }
    }

    for (int i = 1; i <= n; i++){
        p[0][i] = find(a[i].se);
    }
    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);
    for (int i = 1; i <= n; i++){
        if (add(l[i], r[i])){
            ans.push_back(i);
            s.insert({l[i], r[i]});
        }
    }
    if (ans.size() < k){
        printf("-1\n");
    }
    else for (int i = 0; i < k; i++) printf("%d\n",ans[i]);




}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:109:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |     if (ans.size() < k){
      |         ~~~~~~~~~~~^~~
event2.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
event2.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d%d",&l[i], &r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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