oj.uz

Submission #577188

# Submission time Handle Problem Language Result Execution time Memory
577188 2022-06-14T08:49:40 Z dantoh000 Event Hopping 2 (JOI21_event2) C++14
0 / 100
 99 ms 30004 KB 
#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+1;
    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);
    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){
    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;
    });
    a[0] = {0,0};
    a[n+1] = {1000000001,1000000001};
    for (int i = 1; i <= n; i++){
        st[0][i] = a[i].fi;
    }
    for (int k = 1; k < 17; k++){
        for (int i = 0; i <= n+1; i++){
            if (i + (1<<(k-1)) <= n+1){
                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(0, 1000000001);
    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

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Runtime error 99 ms 30004 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Runtime error 99 ms 30004 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -