제출 #577199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
577199		dantoh000	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	234 ms	22520 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 || a[x].fi < l) 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);
    ///printf("%d\n",cur);
    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]);
}

컴파일 시 표준 에러 (stderr) 메시지

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: 7 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 61 / 61