Submission #792570

#	Time	Username	Problem	Language	Result	Execution time	Memory
792570		Cookie	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	149 ms	17324 KiB

event2

#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ll mxn = 3e5 + 5, base = 972663749;
const ll mod = 911382323, mxv = 1e9 + 1, inf = 2e9;
int n, k;
vt<int>comp;
int up[mxn + 1][17],  l[mxn + 1], r[mxn + 1];
vt<pll>seg;
int find(int mn){
    return(lower_bound(comp.begin(), comp.end(), mn) - comp.begin());
}
int get(int l, int r){
    int ans =0 ;
    for(int i = 16; i >= 0; i--){
        if(up[l][i] <= r){
            ans += (1 << i); l = up[l][i];
        }
    }
    return(ans);
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> l[i] >> r[i]; comp.pb(l[i]); seg.pb({l[i], r[i]});
    }
    comp.pb(inf);
    sort(comp.begin(), comp.end());  comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
    sort(seg.rbegin(), seg.rend());
    ll mn = inf, rr = 0;
    up[sz(comp) - 1][0] = sz(comp); up[sz(comp)][0] = sz(comp);
    for(int i = sz(comp) - 2; i >= 0; i--){
        while(rr < sz(seg) && seg[rr].fi == comp[i]){
            mn = min(mn, seg[rr].se); rr++;
        }
        up[i][0] = find(mn);
       
    }
    for(int i = 1; i < 17; i++){
        for(int j = 0; j <= sz(comp); j++){
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    
    set<pair<int, int>>s;
    vt<int>res;
    int ans = get(0, sz(comp) - 1);
    
    if(ans < k){
        cout << -1;
        return(0);
    }
    for(int i = 0; i < n; i++){
        int le, ri;
        if(s.empty()){
            le = 0, ri = sz(comp) - 1;
        }else{
            auto it = s.lower_bound(make_pair(l[i], -1));
           
            if(it == s.end()){
                ri = sz(comp) - 1;
            }else{
                
                int id = (*it).se;
                
                if(r[i] > l[id])continue;
                ri = find(l[id]);
            }
            it = s.upper_bound(make_pair(l[i], -1));
            if(it == s.begin()){
                le = 0;
            }else{
                it--;
                int id = (*it).se;
                
                if(r[id] > l[i])continue;
                le = find(r[id]);
            }
        }
        int nwans = ans;
        nwans -= get(le, ri);
        nwans += get(le, find(l[i])); nwans += get(find(r[i]), ri); nwans++;
        if(nwans >= k){
            res.pb(i); if(sz(res) == k)break;
            s.insert(make_pair(l[i], i));
            ans = nwans;
        }
    }
    for(auto i: res)cout << i + 1 << "\n";
    return(0);
}

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