oj.uz

Submission #947185

# Submission time Handle Problem Language Result Execution time Memory
947185 2024-03-15T15:40:33 Z gesgha Event Hopping 2 (JOI21_event2) C++17
0 / 100
 126 ms 54720 KB 
#include <bits/stdc++.h>
// #pragma GCC target("popcnt")

#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back

#define all(x) x.begin(), x.end()
#define pw(x) (1LL << (x))
#define sz(x) (int)x.size()

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T>
using ve = vector <T>;

template <typename T>
bool umx (T& a, T b) { return a < b ? a = b, 1 : 0; }

template <typename T>
bool umn (T& a, T b) { return a > b ? a = b, 1 : 0; }

using ll = long long;
using ld = long double;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
using ull = unsigned long long;

const int oo = 1e9 + 100;
const ll OO = 1e18;
const int N = 5e5 + 10;
const int M = 3e3 + 10;
const int mod = 998244353;
const bool TEST = 0;

mt19937_64 rng(228);
void precalc() {}




ll mn[N][20];
ll go[N];

int get(int l, int r) {
    int S = 0;
    for (int i = 19; i >= 0; i--) if (mn[l][i] <= r) {
        S += pw(i);
        l = mn[l][i];
    }
    return S;
}

void slv() {
    int n, k;
    cin >> n >> k;
    ve <array <ll, 3>> ev(n);
    ve <array <ll, 3>> V;
    for (int i = 0; i < n; i++) {
        cin >> ev[i][0] >> ev[i][1];
        V.pb({ev[i][0], i, 0});
        V.pb({ev[i][1], i, 1});
    }
    int c = 0;
    {
        sort(all(V));
        ev[V[0][1]][V[0][2]] = c;
        for (int i = 1; i < sz(V); i++) {
            c += bool(V[i][0] != V[i - 1][0]);
            ev[V[i][1]][V[i][2]] = c;
        }   
    }
    fill(go, go + 2 * n + 1, 2 * n);
    for (int i = 0; i < n; i++) {
        umn(go[ev[i][0]], ev[i][1]);
    }
    for (int i = 2 * n - 1; i >= 0; i--) umn(go[i], go[i + 1]);
    for (int i = 0; i < 20; i++) mn[2 * n][i] = 2 * n;
    for (int i = 2*n - 1; i >= 0; i--) {
        mn[i][0] = go[i];
        for (int st = 1; st < 20; st++) mn[i][st] = mn[mn[i][st - 1]][st - 1];
    }
    set <int> L;
    set <int> R;
    int S = get(0, 2 * n - 1);
    if (S < k) {
        cout << "-1\n";
        exit(0);
    }
    ve <int> ans;
    for (int i = 0; i < n; i++) {
        int l = ev[i][0];
        int r = ev[i][1];
        int lt = 0, rt = 2 * n - 1;
        bool ok = 1;
        {
            auto it = L.upper_bound(l);
            if (it != L.end()) ok &= (*it) >= r;
            if(it != L.begin()) {
                --it;
                ok &= ((*it) < l);
            }
            it = R.upper_bound(l);
            if (it != R.end()) {
                ok &= (*it) > r;
            }
        }
        if(!ok) continue;
        int was = get(lt, rt);
        int have = S - was + get(lt, l) + get(r, rt) + 1;
        if (have >= k) {
            S = have;
            L.insert(l);
            R.insert(r);
            ans.pb(i);
        }
        if (sz(ans) == k) {
            break;
        }
    }
    fe(x, ans) {
        cout << x + 1 << '\n';
    }

}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    precalc();
    cout << fixed << setprecision(13);
    int q = 1;
    if (TEST) cin >> q;
    while (q--) slv();
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Incorrect 126 ms 54720 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 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2556 KB Output is correct
8 Incorrect 0 ms 2396 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2556 KB Output is correct
8 Incorrect 0 ms 2396 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

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