Submission #1118479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118479		Zero_OP	Event Hopping 2 (JOI21_event2)	C++14	7 / 100	135 ms	43004 KiB

event2

#include <bits/stdc++.h>

using namespace std;

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true;
    return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true;
    return false;
}

struct fenwick_tree{
    vector<int> bit;
    fenwick_tree(int n) : bit(n + 1, 0) {}

    void update(int i, int v){
        if(i == 0 || i == (int)bit.size()) return;
        for(; i < (int)bit.size(); i += i & (-i)) bit[i] += v;
    }

    void update(int l, int r, int v){
        update(l, +v);
        update(r + 1, -v);
    }

    int query(int i){
        i = min((int)bit.size() - 1, i);
        int sum = 0;
        for(; i > 0; i -= i & (-i)) sum += bit[i];
        return sum;
    }

    int find_l(int x){
        int pos = 0;
        for(int i = 17; i >= 0; --i){
            if(pos + (1 << i) < (int)bit.size() && x > bit[pos + (1 << i)]){
                pos += (1 << i);
                x -= bit[pos];
            }
        }
        return pos + 1;
    }

    int find_r(int x){
        int pos = 0;
        for(int i = 17; i >= 0; --i){
            if(pos + (1 << i) < (int)bit.size() && x >= bit[pos + (1 << i)]){
                pos += (1 << i);
                x -= bit[pos];
            }
        }
        return pos + 1;
    }

    int query(int l, int r){
        if(l > r) return 0;
        return query(r) - query(l - 1);
    }

    void set_value(int id, int value){
        update(id, value - query(id));
    }

    void debug(){
        cout << "fenwick : ";
        for(int i = 1; i < (int)bit.size(); ++i){
            cout << query(i) - query(i - 1) << ' ';
        }
        cout << '\n';
    }
};

struct segment_tree{
    vector<int> st, lazy;

    segment_tree(int n) : st(n << 2, 0), lazy(n << 2) {}

    void down(int id){
        if(lazy[id]){
            st[id << 1] = 1;
            lazy[id << 1] = 1;
            st[id << 1 | 1] = 1;
            lazy[id << 1 | 1] = 1;
            lazy[id] = 0;
        }
    }

    void paint(int id, int l, int r, int u, int v){
        if(u <= l && r <= v) st[id] = 1, lazy[id] = 1;
        else{
            int mid = l + r >> 1;
            down(id);
            if(u <= mid) paint(id << 1, l, mid, u, v);
            if(mid < v)  paint(id << 1 | 1, mid + 1, r, u, v);
            st[id] = st[id << 1] | st[id << 1 | 1];
        }
    }

    int have_colored(int id, int l, int r, int u, int v){
        if(v < l || u > r) return 0;
        if(u <= l && r <= v) return st[id];
        int mid = l + r >> 1;
        down(id);
        return have_colored(id << 1, l, mid, u, v) | have_colored(id << 1 | 1, mid + 1, r, u, v);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N, K;
    cin >> N >> K;

    vector<int> l(N), r(N), v;
    for(int i = 0; i < N; ++i){
        cin >> l[i] >> r[i];
        v.emplace_back(l[i]);
        v.emplace_back(r[i]);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    int bound = (int)v.size();
    vector<int> up(bound + 1, bound + 1), down(bound + 1, 0);
    for(int i = 0; i < N; ++i){
        l[i] = lower_bound(v.begin(), v.end(), l[i]) - v.begin() + 1;
        r[i] = lower_bound(v.begin(), v.end(), r[i]) - v.begin() + 1;
//        cout << l[i] << ' ' << r[i] << '\n';
        minimize(up[l[i]], r[i]);
        maximize(down[r[i]], l[i]);
    }
//    cout << '\n';

    for(int i = bound - 1; i >= 1; --i){
        minimize(up[i], up[i + 1]);
    }

    for(int i = 1; i <= bound; ++i){
        maximize(down[i], down[i - 1]);
    }

//    for(int i = 1; i <= bound; ++i){
//        cout << dbg(up[i]) << dbg(down[i]) << '\n';
//    }

    int L = 32 - __builtin_clz(bound);
    vector<vector<int>> next(L, vector<int>(bound + 1, bound + 1)), prev(L, vector<int>(bound + 1));
    next[0] = up;
    prev[0] = down;
    for(int i = 1; i < L; ++i){
        for(int j = 1; j <= bound; ++j){
            if(next[i - 1][j] == bound + 1) next[i][j] = bound + 1;
            else next[i][j] = next[i - 1][next[i - 1][j]];

            if(prev[i - 1][j] == 0) prev[i][j] = 0;
            else prev[i][j] = prev[i - 1][prev[i - 1][j]];
        }
    }

//    for(int i = 0; i < L; ++i){
//        for(int j = 1; j <= bound; ++j){
//            cout << dbg(i) << dbg(j) << dbg(prev[i][j]) << dbg(next[i][j]) << '\n';
//        }
//    }

    auto greedy_left = [&](int st, int bound_left) -> int{
        if(st < bound_left) return 0;
        int ans = 0;
        for(int i = L - 1; i >= 0; --i){
            if(prev[i][st] >= bound_left){
                ans += (1 << i);
                st = prev[i][st];
            }
        }
        return ans;
    };

    auto greedy_right = [&](int st, int bound_right) -> int{
        if(st > bound_right) return 0;
//        cout << dbg(st) << dbg(bound_right) << '\n';
        int ans = 0;
        for(int i = L - 1; i >= 0; --i){
            if(next[i][st] <= bound_right){
                ans += (1 << i);
                st = next[i][st];
            }
        }
        return ans;
    };

    fenwick_tree ft(bound);
    vector<int> ans;

    int s = -1, prefs = -1, suffs = -1;
    for(int i = 0; i < N; ++i){
        int pref = greedy_left(l[i], 1);
        int suff = greedy_right(r[i], bound);
        if(pref + suff + 1 >= K){
            s = i;
            prefs = pref;
            suffs = suff;
            break;
        }
    }

    if(s == -1){
        cout << -1 << '\n';
        return 0;
    }

    fenwick_tree cover(bound);
    segment_tree online(bound);

    ans.push_back(s);

    cover.update(l[s], prefs);
    cover.update(r[s], suffs);
    ft.update(l[s], +1);
    ft.update(r[s], +1);
//    cout << l[s] << " : " << prefs << '\n';
//    cout << r[s] << " : " << suffs << '\n';
    online.paint(1, 1, bound, l[s], r[s] - 1);

//    ft.debug();
//    cover.debug();

//    cout << dbg(prefs) << dbg(suffs) << '\n';
    int need = K - 1, free = prefs + suffs + 1 - K;
    for(int i = s + 1; i < N && need; ++i){
        int contain = online.have_colored(1, 1, bound, l[i], r[i] - 1);
        if(contain > 0) continue;

//        cout << "passed : " << i << ' ' << dbg(l[i]) << dbg(r[i]) << '\n';

        int cur = ft.query(l[i]);
        int L = ft.find_l(cur);
        int R = min(bound, ft.find_r(cur));

//        cout << dbg(cur) << dbg(L) << dbg(R) << '\n';

        assert(L <= R);

        int pref = greedy_left(l[i], L);
        int suff = greedy_right(r[i], R);
//        cover.debug();
        int delta = -cover.query(L, R) + pref + suff + 1;

//        cout << dbg(pref) << dbg(suff) << dbg(cover.query(L, R)) << '\n';
//        cout << delta << '\n';
        if(delta + free >= 0){
            --need;
            ans.push_back(i);
            cover.set_value(L, 0);
            cover.set_value(R, 0);
            ft.update(l[i], +1);
            ft.update(r[i], +1);
            online.paint(1, 1, bound, l[i], r[i] - 1);
            free += delta;
            if(r[i] <= R) cover.update(r[i], suff);
            if(L <= l[i])  cover.update(l[i], pref);
        }
    }

//    assert((int)ans.size() == K);
    for(auto it : ans) cout << it + 1 << '\n';

    return 0;
}

Compilation message (stderr)

event2.cpp: In member function 'void segment_tree::paint(int, int, int, int, int)':
event2.cpp:98:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |             int mid = l + r >> 1;
      |                       ~~^~~
event2.cpp: In member function 'int segment_tree::have_colored(int, int, int, int, int)':
event2.cpp:109:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |         int mid = l + r >> 1;
      |                   ~~^~~

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