Submission #995963

#	Time	Username	Problem	Language	Result	Execution time	Memory
995963		snpmrnhlol	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	189 ms	28960 KiB

event2

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
const int logN = 20;
const int inf = 2e9;
vector <int> ans;
struct range{
    int l,r,id;
}v[N];
int p[N];
int jump[N][logN];
int mx[N][logN];
int query(int l, int r){
    int nr = 31 - __builtin_clz(r - l + 1);
    return max(mx[l][nr],mx[r - (1<<nr) + 1][nr]);
}
int n,k;
int calc(int ql,int qr){
    int l = 0,r = n;
    while(l != r){
        int mij = (l + r)/2;
        if(query(0,mij) >= ql){
            r = mij;
        }else l = mij + 1;
    }
    //cout<<"calc:"<<ql<<' '<<qr<<' ';
    if(l == n || v[l].r > qr){
        //cout<<0<<'\n';
        return 0;
    }
    int ans = 1;
    for(int i = logN - 1;i >= 0;i--){
        if(jump[l][i] != n && v[jump[l][i]].r <= qr){
            ans+=(1<<i);
            l = jump[l][i];
        }
    }
    //cout<<ans<<'\n';
    return ans;
}
map <int,int> segments;
int main(){
    cin>>n>>k;
    for(int i = 0;i < n;i++){
        cin>>v[i].l>>v[i].r;
        v[i].r--;
        v[i].id = i;
    }
    sort(v, v + n, [&](range a,range b){
         return a.r < b.r;
    });
    for(int i = 0;i < n;i++){
        p[v[i].id] = i;
        mx[i][0] = v[i].l;
    }
    for(int j = 1;j < logN;j++){
        for(int i = 0;i < n - (1<<j) + 1;i++){
            mx[i][j] = max(mx[i][j - 1],mx[i + (1<<(j - 1))][j - 1]);
        }
    }
    for(int i = 0;i < n;i++){
        int l = i + 1,r = n;
        while(l != r){
            int mij = (l + r)/2;
            if(query(0,mij) > v[i].r){
                r = mij;
            }else l = mij + 1;
        }
        jump[i][0] = l;
    }
    for(int j = 1;j < logN;j++){
        for(int i = 0;i < n;i++){
            if(jump[i][j - 1] == n)jump[i][j] = n;
            else jump[i][j] = jump[jump[i][j - 1]][j - 1];
        }
    }
    segments[0] = 0;
    segments[inf] = inf;
    int cur = calc(0,inf);
    for(int i = 0;i < n;i++){
        int id = p[i];
        //cout<<v[id].l<<' '<<v[id].r<<' '<<cur<<'\n';
        auto it = segments.lower_bound(v[id].l);
        bool ok = 1;
        if(prev(it)->second >= v[id].l){
            ok = 0;
        }
        if(it->first <= v[id].r){
            ok = 0;
        }
        if(!ok)continue;
        int sv = cur;
        cur-=calc(prev(it)->second + 1,it->first - 1);
        cur+=calc(prev(it)->second + 1,v[id].l - 1);
        cur+=calc(v[id].r + 1,it->first - 1);
        cur++;
        //cout<<"consideration:"<<sv<<' '<<cur<<' '<<i<<'\n';
        if(cur >= k){
            //cout<<"add\n";
            ans.push_back(i + 1);
            segments[v[id].l] = v[id].r;
        }else cur = sv;
    }
    if(ans.size() >= k){
        for(int i = 0;i < k;i++){
            cout<<ans[i]<<'\n';
        }
    }else cout<<-1<<'\n';
    return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:104:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  104 |     if(ans.size() >= k){
      |        ~~~~~~~~~~~^~~~

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