oj.uz

답안 #1026480

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1026480 2024-07-18T06:43:31 Z gyg Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 14200 KB 
#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 >> 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);
        cout << ((dp[s] >= INF) ? "impossible" : to_string(dp[s])) << '\n';
    }
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Execution timed out 1594 ms 12172 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 3 ms 4440 KB Output is correct
3 Correct 70 ms 4444 KB Output is correct
4 Correct 67 ms 4440 KB Output is correct
5 Correct 68 ms 4444 KB Output is correct
6 Correct 70 ms 4440 KB Output is correct
7 Correct 76 ms 4700 KB Output is correct
8 Correct 98 ms 4700 KB Output is correct
9 Correct 59 ms 4444 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 3 ms 4440 KB Output is correct
3 Correct 70 ms 4444 KB Output is correct
4 Correct 67 ms 4440 KB Output is correct
5 Correct 68 ms 4444 KB Output is correct
6 Correct 70 ms 4440 KB Output is correct
7 Correct 76 ms 4700 KB Output is correct
8 Correct 98 ms 4700 KB Output is correct
9 Correct 59 ms 4444 KB Output is correct
10 Correct 2 ms 4440 KB Output is correct
11 Correct 3 ms 4444 KB Output is correct
12 Correct 70 ms 4444 KB Output is correct
13 Correct 72 ms 4444 KB Output is correct
14 Correct 64 ms 4444 KB Output is correct
15 Correct 64 ms 4444 KB Output is correct
16 Correct 75 ms 4608 KB Output is correct
17 Correct 76 ms 4700 KB Output is correct
18 Correct 53 ms 4444 KB Output is correct
19 Execution timed out 1546 ms 5308 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 3 ms 4440 KB Output is correct
3 Correct 70 ms 4444 KB Output is correct
4 Correct 67 ms 4440 KB Output is correct
5 Correct 68 ms 4444 KB Output is correct
6 Correct 70 ms 4440 KB Output is correct
7 Correct 76 ms 4700 KB Output is correct
8 Correct 98 ms 4700 KB Output is correct
9 Correct 59 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 3 ms 4444 KB Output is correct
12 Correct 69 ms 4444 KB Output is correct
13 Correct 71 ms 4444 KB Output is correct
14 Correct 68 ms 4444 KB Output is correct
15 Correct 70 ms 4444 KB Output is correct
16 Correct 77 ms 4700 KB Output is correct
17 Correct 73 ms 4700 KB Output is correct
18 Correct 55 ms 4444 KB Output is correct
19 Execution timed out 1575 ms 14200 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1540 ms 12328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Execution timed out 1594 ms 12172 KB Time limit exceeded
3 Halted 0 ms 0 KB -