Submission #973182

#	Time	Username	Problem	Language	Result	Execution time	Memory
973182		underwaterkillerwhale	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	456 ms	52524 KiB

event2

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 5e5 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const int INF = 2e9 + 7;
const int BASE = 137;

struct Segment_Tree {
    int Range;
    ll st[N << 2], lz[N << 2];

    void init (int n) {
        Range = n;
    }
    void down (int id, int l, int r) {
        int mid = l + r >> 1;
        st[id << 1] += lz[id] * (mid - l + 1);
        lz[id << 1] += lz[id];

        st[id << 1 | 1] += lz[id] * (r - mid);
        lz[id << 1 | 1] += lz[id];

        lz[id] = 0;
    }
    void update (int id, int l, int r, int u, int v, int val) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            st[id] += val * (r - l + 1);
            lz[id] += val;
            return;
        }
        int mid = l + r >> 1;
        down (id, l, r);
        update (id << 1, l, mid, u, v, val);
        update (id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }
    void Assign (int id, int l, int r, int pos, int val) {
        if (l > pos || r < pos) return;
        if (l == r) {
            st[id] = val;
            return;
        }
        int mid = l + r >> 1;
        down (id, l, r);
        Assign (id << 1, l, mid, pos, val);
        Assign (id << 1 | 1, mid + 1, r, pos, val);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }
    ll get (int id, int l, int r, int u, int v) {
        if (l > v || r < u) return 0;
        if (l >= u && r <= v) return st[id];
        int mid = l + r >> 1;
        down (id, l, r);
        return get (id << 1, l, mid, u, v) + get (id << 1 | 1, mid + 1, r, u, v);
    }

    void update (int u, int v, int val) {
        update (1, 1, Range, u, v, val);
    }
    void Assign (int pos, int val) {
        Assign (1, 1,  Range, pos, val);
    }
    ll get (int u, int v) {
        return get (1, 1, Range, u, v);
    }
}pre, suf, Fixed;

int n, K;
pair<int,int> a[N];
pair<int,int> toIT[N];
int spt[N][25];

vector<int> rar;
int numVal;
int mnsuf[N];

void compress () {
    rep (i, 1, n) rar.push_back(a[i].fs), rar.push_back(a[i].se);
    sort (ALL(rar));
    rar.resize(numVal = unique(ALL(rar)) - rar.begin());
    rep (i, 1, n)
        a[i].fs = lower_bound(ALL(rar), a[i].fs) - rar.begin() + 1,
        a[i].se = lower_bound(ALL(rar), a[i].se) - rar.begin() + 1;
}

void solution() {
    cin >> n >> K;
    rep (i, 1, n) {
        cin >> a[i].fs >> a[i].se;
    }
    compress();
//    rep (i, 1, n) {
//        cout << a[i].fs <<","<<a[i].se <<"\n";
//    }
    rep (i, 0, numVal + 1) mnsuf[i] = numVal + 2;
    rep (i, 1, n)
        mnsuf[a[i].fs] = min (mnsuf[a[i].fs], a[i].se);
    rep (i, 0, numVal)
        mnsuf[i] = min (mnsuf[i + 1], mnsuf[i]);
    rep (i, 0, numVal)
        spt[i][0] = mnsuf[i];
    rep (j, 1, 20)
    rep (i, 0, numVal) spt[i][j] = spt[spt[i][j - 1]][j - 1];

    pre.init(numVal);
    suf.init(numVal);
    Fixed.init(numVal);

    vector<int> Ans;
    function<int(int L, int R)> numIT = [] (int L, int R) {
        int start = L, res = 0;
        reb (i, 20, 0) {
            if (spt[start][i] <= R) {
                start = spt[start][i];
                res += (1 << i);
            }
        }
        return res;
    };
    rep (i, 1, n) {
        if (SZ(Ans) == K) break;
        int L = a[i].fs, R = a[i].se;
        if (Fixed.get (L + 1, R - 1)) {
            continue;
        }
        function<int()> val_Left = [&] () {
            if (Fixed.get (1, L) == 0) return 0;
            int lf = 1, rt = L;
            while (lf < rt) {
                int mid = lf + rt + 1 >> 1;
                if (Fixed.get (mid, L) >= 1) lf = mid;
                else rt = mid - 1;
            }
            return lf;
        };
        function<int()> val_Right = [&] () {
            if (Fixed.get (R, numVal) == 0) return numVal + 1;
            int lf = R, rt = numVal;
            while (lf < rt) {
                int mid = lf + rt >> 1;
                if (Fixed.get (R, mid) >= 1) rt = mid;
                else lf = mid + 1;
            }
            return rt;
        };
        int Left = val_Left(), Right = val_Right();
        int valLR = numIT (Left, Right),
            nvalLR = 1 + numIT(Left, L) + numIT(R, Right);
        if (pre.get(Left, Left) + suf.get(Right, Right) + nvalLR >= K) {
            Fixed.update (L, R, 1);
            suf.update (1, Left, -valLR + nvalLR);
            pre.update (Right, numVal, -valLR + nvalLR);
            pre.Assign (R, pre.get(Left, Left) + numIT(Left, L) + 1);
            suf.Assign (L, suf.get(Right, Right) + numIT(R, Right) + 1);
            Ans.push_back(i);
        }
    }
    if (SZ(Ans) < K) cout << -1 <<"\n";
    else {
        iter (&id, Ans) cout << id <<"\n";
    }

}


#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
14 3
74 17 88 80 70 24 66 29 24 63 84 36 72 43
*/

Compilation message (stderr)

event2.cpp: In member function 'void Segment_Tree::down(int, int, int)':
event2.cpp:34:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int mid = l + r >> 1;
      |                   ~~^~~
event2.cpp: In member function 'void Segment_Tree::update(int, int, int, int, int, int)':
event2.cpp:50:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |         int mid = l + r >> 1;
      |                   ~~^~~
event2.cpp: In member function 'void Segment_Tree::Assign(int, int, int, int, int)':
event2.cpp:62:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         int mid = l + r >> 1;
      |                   ~~^~~
event2.cpp: In member function 'long long int Segment_Tree::get(int, int, int, int, int)':
event2.cpp:71:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         int mid = l + r >> 1;
      |                   ~~^~~
event2.cpp: In lambda function:
event2.cpp:149:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  149 |                 int mid = lf + rt + 1 >> 1;
      |                           ~~~~~~~~^~~
event2.cpp: In lambda function:
event2.cpp:159:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  159 |                 int mid = lf + rt >> 1;
      |                           ~~~^~~~

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