oj.uz

Submission #1026483

# Submission time Handle Problem Language Result Execution time Memory
1026483 2024-07-18T06:45:40 Z gyg Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 12372 KB 
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>    
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 1e5 + 5, INF = 1e9;

int n, q;
array<int, MAX_N> l, r;

vector<pii> ord; // {r, i}
int n_ccs;
unordered_map<int, int> cc;
void precomp() {
    for (int i = 1; i <= n; i++) ord.push_back({r[i], i});
    sort(ord.rbegin(), ord.rend());

    set<int> coords;
    for (int i = 1; i <= n; i++) coords.insert(l[i]), coords.insert(r[i]);
    while (coords.size()) {
        n_ccs++, cc[*coords.begin()] = n_ccs;
        coords.erase(coords.begin());
    }
}

array<int, 8 * MAX_N> st;
void update(int l, int r, int x, int u = 1, int lo = 1, int hi = n_ccs) {
    if (r < lo || hi < l) return;
    if (l <= lo && hi <= r) { st[u] = min(st[u], x); return; }
    int mid = (lo + hi) / 2;
    update(l, r, x, 2 * u, lo, mid), update(l, r, x, 2 * u + 1, mid + 1, hi);
}
int query(int i, int u = 1, int lo = 1, int hi = n_ccs) {
    if (i < lo || hi < i) return INF;
    if (lo == hi) return st[u];
    int mid = (lo + hi) / 2;
    return min({st[u], query(i, 2 * u, lo, mid), query(i, 2 * u + 1, mid + 1, hi)});
}

array<int, MAX_N> dp;
void comp(int f) {
    fill(st.begin(), st.end(), INF);

    for (pii x : ord) {
        int i = x.second;
        if (i == f) dp[i] = 0;
        else if (l[f] <= r[i] && r[i] <= r[f]) dp[i] = 1;
        else dp[i] = query(cc[r[i]]) + 1;
        update(cc[l[i]], cc[r[i]], dp[i]);
    }
} 

int main() {
    // freopen("event.in", "r", stdin);
    cin.sync_with_stdio(false), cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
    
    precomp();

    for (int i = 1; i <= q; i++) {
        int s, f; cin >> s >> f;
        comp(f);
        if (dp[s] >= INF) cout << "impossible" << '\n';
        else cout << dp[s] << '\n';
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Execution timed out 1589 ms 12372 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 16 ms 4444 KB Output is correct
4 Correct 18 ms 4648 KB Output is correct
5 Correct 18 ms 4444 KB Output is correct
6 Correct 18 ms 4444 KB Output is correct
7 Correct 27 ms 4696 KB Output is correct
8 Correct 23 ms 4700 KB Output is correct
9 Correct 7 ms 4440 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 16 ms 4444 KB Output is correct
4 Correct 18 ms 4648 KB Output is correct
5 Correct 18 ms 4444 KB Output is correct
6 Correct 18 ms 4444 KB Output is correct
7 Correct 27 ms 4696 KB Output is correct
8 Correct 23 ms 4700 KB Output is correct
9 Correct 7 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 16 ms 4444 KB Output is correct
13 Correct 17 ms 4652 KB Output is correct
14 Correct 17 ms 4644 KB Output is correct
15 Correct 17 ms 4644 KB Output is correct
16 Correct 25 ms 4700 KB Output is correct
17 Correct 22 ms 4696 KB Output is correct
18 Correct 8 ms 4444 KB Output is correct
19 Execution timed out 1591 ms 5092 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 16 ms 4444 KB Output is correct
4 Correct 18 ms 4648 KB Output is correct
5 Correct 18 ms 4444 KB Output is correct
6 Correct 18 ms 4444 KB Output is correct
7 Correct 27 ms 4696 KB Output is correct
8 Correct 23 ms 4700 KB Output is correct
9 Correct 7 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 16 ms 4648 KB Output is correct
13 Correct 22 ms 4444 KB Output is correct
14 Correct 18 ms 4440 KB Output is correct
15 Correct 17 ms 4444 KB Output is correct
16 Correct 25 ms 4716 KB Output is correct
17 Correct 22 ms 4696 KB Output is correct
18 Correct 8 ms 4444 KB Output is correct
19 Execution timed out 1598 ms 12228 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1549 ms 12336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Execution timed out 1589 ms 12372 KB Time limit exceeded
3 Halted 0 ms 0 KB -