oj.uz

Submission #415034

# Submission time Handle Problem Language Result Execution time Memory
415034 2021-05-31T13:02:22 Z 최서현(#7466) Event Hopping 2 (JOI21_event2) C++17
0 / 100
 82 ms 11704 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <set>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG

using namespace std;

const int INF = (int)1e9 + 7;
pii X[101010];
int sp[101010][20];

int qry(int l, int r)
{
    if(l == r) return 0;
    int ret = 1;
    for(int i = 19; i >= 0; --i) if(sp[l][i] < r) l = sp[l][i], ret += (1 << i);
    return ret;
}

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

    int n, k; cin >> n >> k;
    int N = n + 2; k += 2;
    pii A[n]; for(auto &i : A) cin >> i.ff >> i.ss;
    piii B[N]; for(int i = 0; i < n; ++i) B[i] = {A[i].ss, {A[i].ff, i}};
    B[n] = {-INF, {-INF, n}}, B[n + 1] = {INF, {INF, n}};
    sort(B, B + N);
    int C[n]; for(int i = 0; i < N; ++i) if(B[i].rr < n) C[B[i].rr] = i;
    for(int i = 0; i < N; ++i) X[i] = {B[i].ee, B[i].ff};

    queue<pii> Q;
    for(int i = 0; i < N; ++i)
    {
        while(Q.size() && Q.front().ff <= X[i].ff) sp[Q.front().ss][0] = i, Q.pop();
        Q.push({X[i].ss, i});
    }
    while(Q.size()) sp[Q.front().ss][0] = INF, Q.pop();

    for(int i = 1; i < 20; ++i) for(int j = 0; j < N; ++j)
        sp[j][i] = (sp[j][i - 1] == INF ? INF : sp[sp[j][i - 1]][i - 1]);

    int ans = qry(0, N);
    if(ans < k) { cout << -1; return 0; }

    set<pii> S;
    S.insert({0, N});
    int cnt = k - 2;
    for(int i = 0; i < n; ++i)
    {
        if(cnt == 0) return 0;
        int l = upper_bound(B, B + N, piii{X[C[i]].ff, pii{INF, INF}}) - B;
        int r = sp[C[i]][0];
        auto it = S.upper_bound({l, INF});
//        if(it != S.end()) cout << i << ' ' << it->ff << ' ' << it->ss << endl;
        if(it == S.begin() || prev(it)->ff > l || prev(it)->ss < r) continue;
        --it;
        int s = it->ff, e = it->ss;
        int _ans = ans;
        _ans -= qry(s, e);
        _ans += qry(s, l);
        _ans += qry(r, e);
        ++_ans;
        if(_ans < k) continue;
        cout << i + 1 << '\n';
        ans = _ans;
        S.erase(it);
        if(s < l) S.insert({s, l});
        if(r < e) S.insert({r, e});
        --cnt;
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 82 ms 11704 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 82 ms 11704 KB Output isn't correct
5 Halted 0 ms 0 KB -