Submission #1163680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163680		HasanV11010238	Event Hopping 2 (JOI21_event2)	C++20	100 / 100	590 ms	103332 KiB

event2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> tr, L, R;
int nxt = 1;
int next(){
    nxt++;
    return nxt;
}
int update(int v, int l, int r, int pos, int val){
    int nv = next();
    L[nv] = L[v], R[nv] = R[v];
    if (l == r){
        tr[nv] = val;
        return nv;
    }
    int mid = (l + r) / 2;
    if (pos <= mid){
        L[nv] = update(L[nv], l, mid, pos, val);
    }
    else{
        R[nv] = update(R[nv], mid + 1, r, pos, val);
    }
    tr[nv] = tr[L[nv]] + tr[R[nv]];
    return nv;
}
int query(int v, int l, int r, int ql, int qr){
    if (l > qr || r < ql || v == 0){
        return 0;
    }
    if (ql <= l && r <= qr){
        return tr[v];
    }
    int mid = (l + r) / 2;
    return query(L[v], l, mid, ql, qr) + query(R[v], mid + 1, r, ql, qr);
}
vector<ll> f, lz;
int m;
void relax(int v, int l, int r){
    f[v] += lz[v] * (r - l + 1);
    if (l != r){
        lz[v * 2] += lz[v], lz[v * 2 + 1] += lz[v];
    }
    lz[v] = 0;
}
void upd(int v, int l, int r, int ql, int qr){
    relax(v, l, r);
    if (l > qr || r < ql){
        return;
    }
    if (ql <= l && r <= qr){
        lz[v]++;
        relax(v, l, r);
        return;
    }
    int mid = (l + r) / 2;
    upd(v * 2, l, mid, ql, qr);
    upd(v * 2 + 1, mid + 1, r, ql, qr);
    f[v] = f[v * 2] + f[v * 2 + 1];
}
int qu(int v, int l, int r, int ql, int qr){
    relax(v, l, r);
    if (l > qr || r < ql || ql > qr){
        return 0;
    }
    if (ql <= l && r <= qr){
        return f[v];
    }
    int mid = (l + r) / 2;
    return qu(v * 2, l, mid, ql, qr) + qu(v * 2 + 1, mid + 1, r, ql, qr);
}
int main(){
    int n, k, l, r;
    cin>>n>>k;
    set<int> se, se2;
    map<int, int> ma;
    vector<int> le(n + 1, 0), ri(n + 1, 0);
    tr.assign(5000000, 0), L.assign(5000000, 0), R.assign(5000000, 0);
    for (int i = 1; i <= n; i++){
        cin>>le[i]>>ri[i];
        se.insert(le[i]);
        se.insert(ri[i]);
    }
    int no = 1;
    for (auto el : se){
        ma[el] = no;
        no++;
    }
    no += 3;
    m = no;
    f.assign(4 * m + 4, 0);
    lz.assign(4 * m + 4, 0);
    vector<int> ev(m + 1, 0), ha(m + 1, 0);
    for (int i = 1; i <= n; i++){
        le[i] = ma[le[i]];
        ri[i] = ma[ri[i]];
        ev[ri[i]] = max(ev[ri[i]], le[i]);
        ha[ri[i]] = 1;
    }
    vector<int> ro(m + 1, 1);
    for (int i = 2; i <= m; i++){
        int q = query(ro[i - 1], 0, m, ev[i], i);
        if (ha[i] == 0 || q > 0){
            ro[i] = ro[i - 1];
        }
        else{
            ro[i] = update(ro[ev[i]], 0, m, ev[i], 1);
        }
    }
    se.clear();
    se.insert(m);
    se.insert(1);
    se2.insert(-1);
    se2.insert(-m);
    vector<int> ans, lv(m + 1, 0);
    ll su = query(ro[m], 0, m, 1, m);
    for (int i = 1; i <= n; i++){
        if (k == 0 || su < k){
            break;
        }
        l = le[i], r = ri[i];
        if (qu(1, 1, m, l + 1, r - 1) > 0) continue;
        int lb = -*se2.lower_bound(-l);
        int rb = *se.lower_bound(r);
        if (lv[lb] == 1) continue;
        ll ch = query(ro[l], 0, m, lb, l) + query(ro[rb], 0, m, r, rb) - query(ro[rb], 0, m, lb, rb);
        su += ch;
        if (su + 1 >= k){
            k--;
            ans.push_back(i);
            se.insert(l);
            se.insert(r);
            se2.insert(-l);
            se2.insert(-r);
            lv[l] = 1;
            upd(1, 1, m, l, r);
        }
        else{
            su -= ch;
        }
    }
    if (k != 0){
        cout<<-1<<"\n";
        return 0;
    }
    for (auto el : ans){
        cout<<el<<"\n";
    }
}

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