Submission #1118292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118292		Zero_OP	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	54 ms	14420 KiB

event2

#include <bits/stdc++.h>

using namespace std;

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

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

    void update(int i, int v){
        for(; i > 0; i -= i & (-i)) bit[i] = max(bit[i], v);
    }

    int query(int i){
        int best = 0;
        for(; i < (int)bit.size(); i += i & (-i)) best = max(best, bit[i]);
        return best;
    }
};

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;

    struct event{
        int l, r, id;
        event(int l, int r, int id) : l(l), r(r), id(id) {}
        bool operator < (const event& o){
            if(l != o.l) return l < o.l;
            if(r != o.r) return r < o.r;
            return id < o.id;
        }
    };

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

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

    max_suffix_fenwick ft((int)v.size());

    vector<int> dp(N);
    vector<int> pos;

    for(int i = 0; i < N; ++i){
        int l = lower_bound(v.begin(), v.end(), events[i].l) - v.begin() + 1;
        int r = lower_bound(v.begin(), v.end(), events[i].r) - v.begin() + 1;
        int id = events[i].id;

        events[i] = event(l, r, id);
    }

    sort(events.begin(), events.end());
    for(int i = N - 1; i >= 0; --i){
        int l = events[i].l, r = events[i].r;
        dp[i] = ft.query(r) + 1;
        ft.update(l, dp[i]);

        if(pos.empty() || dp[pos.back()] <= dp[i]) pos.push_back(i);
    }

    if(dp[pos.back()] < K){
        cout << -1 << '\n';
        return 0;
    }

    reverse(pos.begin(), pos.end());

    vector<int> ans;

    auto search_last = [&](int l, int r, int x){
        int ans = N - 1;
        while(l <= r){
            int mid = l + r >> 1;
            if(dp[pos[mid]] >= x) ans = mid, l = mid + 1;
            else r = mid - 1;
        }
        return ans;
    };

    auto search_first = [&](int l, int r, int x){
        int ans = N;
        while(l <= r){
            int mid = l + r >> 1;
            if(events[pos[mid]].l >= x) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        return ans;
    };

    int bound = (int)pos.size();
    int L = 32 - __builtin_clz(bound);

    vector<int> pos_in_events(N);
    for(int i = 0; i < bound; ++i){
        pos_in_events[events[pos[i]].id] = i;
    }

    vector<vector<int>> rmq(L, vector<int>(bound));
    for(int i = 0; i < bound; ++i) rmq[0][i] = events[pos[i]].id;
    for(int i = 1; i < L; ++i){
        for(int j = 0; j + (1 << i) <= bound; ++j){
            rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
        }
    }
  
    auto get_min = [&](int l, int r) -> int{
        int k = 31 - __builtin_clz(r - l);
        return min(rmq[k][l], rmq[k][r - (1 << k)]);
    };

    int target = K;
    for(int i = 0; i < (int)pos.size();){
        int j = 1 + search_last(i, (int)pos.size() - 1, target);

        --target;
        int cur = get_min(i, j);
        int x = pos_in_events[cur];
        ans.emplace_back(cur);

        if(j == (int)pos.size()) break;

        j = search_last(i, (int)pos.size() - 1, dp[pos[i]]);
        i = search_first(j, (int)pos.size() - 1, events[pos[x]].r);
    }

    assert((int)ans.size() == K);
    sort(ans.begin(), ans.end());
    for(auto x : ans){
        cout << x + 1 << '\n';
    }

    return 0;
}

Compilation message (stderr)

event2.cpp: In lambda function:
event2.cpp:91:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |             int mid = l + r >> 1;
      |                       ~~^~~
event2.cpp: In lambda function:
event2.cpp:101:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |             int mid = l + r >> 1;
      |                       ~~^~~

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