Submission #966855

#	Time	Username	Problem	Language	Result	Execution time	Memory
966855		Trisanu_Das	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	165 ms	35768 KiB

event2

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(a) begin(a),end(a)
const int N = (int)2e5+5, Lg = 17;
int n, k;
vector<int> v;
set<pair<int,int>> S;
int L[N], R[N], J[Lg][N*2];
 
int get(int l, int r){
    int T = 0;
    for(int i = Lg-1; i>=0; i--)
        if(J[i][l]<=r) l=J[i][l], T+=(1<<i);
    return T;
}
 
int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> L[i] >> R[i], v.pb(L[i]), v.pb(R[i]);
    sort(all(v)); v.erase(unique(all(v)),end(v));
    int m = v.size();
    for(int i = 0; i <= m; i++) J[0][i]=m;
    for(int i = 1; i <= n; i++){
        L[i] = lower_bound(all(v),L[i])-begin(v);
        R[i] = lower_bound(all(v),R[i])-begin(v);
        J[0][L[i]] = min(J[0][L[i]],R[i]);
    }
    for(int i = m-1; i>=0; i--)
        J[0][i]=min(J[0][i],J[0][i+1]);
    for(int i = 1; i < Lg; i++)
        for(int j = 0; j <= m; j++)
            J[i][j] = J[i-1][J[i-1][j]];
    int T = get(0,m-1); if(T<k){cout<<-1;return 0;}
    S.insert({0,0}), S.insert({m-1,m-1});
    for(int i = 1; i <= n; i++){
        auto it = S.lower_bound({R[i],0});
        int r = it->first, l = (--it)->second;
        int num = T-get(l,r)+get(l,L[i])+get(R[i],r)+1;
        if(L[i]>=l and num>=k){
            cout << i << "\n"; T=num;
            S.insert({L[i],R[i]});
            if(S.size()==k+2) break;
        }
    }
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:44:24: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |             if(S.size()==k+2) break;
      |                ~~~~~~~~^~~~~

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