oj.uz

Submission #1094644

# Submission time Handle Problem Language Result Execution time Memory
1094644 2024-09-30T07:58:05 Z not_amir Event Hopping (BOI22_events) C++14
20 / 100
 233 ms 21088 KB 
#include <bits/stdc++.h>
using namespace  std;

typedef pair<int, int> pii;
constexpr int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    vector<pair<pii, int>> events(n);
    vector<int> start(n), end(n);
    map<int, int> mp;
    for(int i = 0; i < n; i++) {
        cin >> start[i] >> end[i];
        events[i].first = {end[i], start[i]};
        mp[start[i]] = mp[end[i]] = 1;
        events[i].second = i;
    }
    int t = 0;
    for(auto& [x, cmp] : mp)
        cmp = t++;
    sort(events.begin(), events.end());
    int N = 1 << 32 - __builtin_clz(t - 1);
    vector<pii> st(2 * N, {INF, -1});
    vector<int> parent(n), jump(n), depth(n);
    for(int i = 0; i < n; i++) {
        int e = events[i].first.first, s = events[i].first.second;
        pii ans = {INF, -1};
        for(int l = N + mp[s], r = 2 * N; l < r; l >>= 1, r >>= 1) {
            if(l & 1) ans = min(ans, st[l++]);
            if(r & 1) ans = min(ans, st[--r]);
        }
        int v = events[i].second;
        if(ans.second == -1 || ans.first >= s)
            jump[v] = parent[v] = v;
        else {
            int p = parent[v] = ans.second;
            depth[v] = depth[p] + 1;
            if(depth[p] - depth[jump[p]] == depth[jump[p]] - depth[jump[jump[p]]])
                jump[v] = jump[jump[p]];
            else
                jump[v] = p;
        }
        for(int j = N + mp[e]; j > 0; j >>= 1)
            st[j] = min(st[j], {mp[s], v});
    }
    while(q--) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        int d = depth[y];
        while(x != y && parent[y] != y && start[parent[y]] >= start[x]) {
            if(start[jump[y]] > start[x])
                y = jump[y];
            else
                y = parent[y];
        }
        if(end[x] >= start[y] && end[x] <= end[y])
            cout << (x!=y) + d - depth[y] << '\n';
        else
            cout << "impossible\n";
    }
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:22:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |     for(auto& [x, cmp] : mp)
      |               ^
events.cpp:25:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   25 |     int N = 1 << 32 - __builtin_clz(t - 1);
      |                  ~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 160 ms 13964 KB Output is correct
3 Correct 170 ms 14004 KB Output is correct
4 Correct 178 ms 13816 KB Output is correct
5 Incorrect 160 ms 14424 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 13912 KB Output is correct
2 Correct 172 ms 13912 KB Output is correct
3 Correct 160 ms 13912 KB Output is correct
4 Correct 141 ms 21088 KB Output is correct
5 Correct 145 ms 14168 KB Output is correct
6 Correct 206 ms 20932 KB Output is correct
7 Correct 198 ms 20772 KB Output is correct
8 Correct 164 ms 20968 KB Output is correct
9 Correct 147 ms 19016 KB Output is correct
10 Correct 217 ms 20556 KB Output is correct
11 Correct 176 ms 20304 KB Output is correct
12 Correct 233 ms 20528 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 160 ms 13964 KB Output is correct
3 Correct 170 ms 14004 KB Output is correct
4 Correct 178 ms 13816 KB Output is correct
5 Incorrect 160 ms 14424 KB Output isn't correct
6 Halted 0 ms 0 KB -