Submission #973254

#	Time	Username	Problem	Language	Result	Execution time	Memory
973254		underwaterkillerwhale	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	1094 ms	86988 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;
        rep (i, 0, n << 2) st[i] = 0, lz[i] = 0;
    }
    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;

struct Segment_Tree1 {
    int Range;
    ll st[N << 2];

    void init (int n) {
        Range = n;
    }
    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;
        Assign (id << 1, l, mid, pos, val);
        Assign (id << 1 | 1, mid + 1, r, pos, val);
        st[id] = max(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;
        return max(get (id << 1, l, mid, u, v), get (id << 1 | 1, mid + 1, r, u, v));
    }

    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);
    }
}mx;

int n, K;
pair<int,int> a[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, 0, numVal + 2) mnsuf[i] = numVal + 2;
    rep (i, 1, n)
        mnsuf[a[i].fs] = min (mnsuf[a[i].fs], a[i].se);
    reb (i, numVal, 0)
        mnsuf[i] = min (mnsuf[i + 1], mnsuf[i]);
    rep (i, 0, numVal + 2) {
        spt[i][0] = mnsuf[i];
//        cout << spt[i][0] <<" ";
    }
//    cout <<"\n";
    rep (j, 1, 20)
    rep (i, 0, numVal + 2) spt[i][j] = spt[spt[i][j - 1]][j - 1];
//    rep (i, 0, 20) cout << spt[5][i] <<" "<<spt[17][1] <<"\n";
    pre.init(numVal);
    suf.init(numVal);
    Fixed.init(numVal);
    mx.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) {
//                cout << start <<" "<<i<<" "<<spt[start][i]<<" "<<R <<"\n";
                start = spt[start][i];
                res += (1 << i);
            }
        }
        return res;
    };
//    cout << numIT (5, 19) <<"\n";
//    return;
    function<bool(int i)> check = [&] (int i) {
        iter (&id, Ans) {
            if (a[id].fs <= a[i].fs && a[id].se > a[i].fs)
                return 0;
        }
        return 1;
    };
    rep (i, 1, n) {
        if (SZ(Ans) == K) break;
        int L = a[i].fs, R = a[i].se;
        if (mx.get(1, L) > L || Fixed.get(L + 1, R - 1))  {
//            cout << i <<" hihi\n";
            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);
//        cout << i<<":"<<Left <<" "<<Right<<"\n";
        if (pre.get(Left, Left) + suf.get(Right, Right) + nvalLR >= K) {
//            cout << i <<": "<<pre.get(Left, Left) <<" "<<suf.get(Right, Right) <<" "<<nvalLR<<"\n";
            Fixed.update (L, R, 1);
            mx.Assign (L, R);
            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();
}
/*
18 3
2 5
6 21
13 19
9 17
14 17
19 20
2 16
2 10
9 14
19 20
14 16
1 3
17 19
14 21
18 19
4 7
5 12
1 13

*/

Compilation message (stderr)

event2.cpp: In member function 'void Segment_Tree::down(int, int, int)':
event2.cpp:35:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int mid = l + r >> 1;
      |                   ~~^~~
event2.cpp: In member function 'void Segment_Tree::update(int, int, int, int, int, int)':
event2.cpp:51:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         int mid = l + r >> 1;
      |                   ~~^~~
event2.cpp: In member function 'void Segment_Tree::Assign(int, int, int, int, int)':
event2.cpp:63:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         int mid = l + r >> 1;
      |                   ~~^~~
event2.cpp: In member function 'long long int Segment_Tree::get(int, int, int, int, int)':
event2.cpp:72:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         int mid = l + r >> 1;
      |                   ~~^~~
event2.cpp: In member function 'void Segment_Tree1::Assign(int, int, int, int, int)':
event2.cpp:101:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |         int mid = l + r >> 1;
      |                   ~~^~~
event2.cpp: In member function 'long long int Segment_Tree1::get(int, int, int, int, int)':
event2.cpp:109:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |         int mid = l + r >> 1;
      |                   ~~^~~
event2.cpp: In lambda function:
event2.cpp:193:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  193 |                 int mid = lf + rt + 1 >> 1;
      |                           ~~~~~~~~^~~
event2.cpp: In lambda function:
event2.cpp:203:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  203 |                 int mid = lf + rt >> 1;
      |                           ~~~^~~~

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