oj.uz

Submission #1094651

# Submission time Handle Problem Language Result Execution time Memory
1094651 2024-09-30T08:16:43 Z not_amir Event Hopping (BOI22_events) C++14
20 / 100
 228 ms 19792 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 >= mp[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(!(end[x] >= start[y] && end[x] <= end[y]) && 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 153 ms 13592 KB Output is correct
3 Correct 156 ms 13764 KB Output is correct
4 Correct 152 ms 13652 KB Output is correct
5 Incorrect 164 ms 14228 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 348 KB Output is correct
2 Correct 0 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 560 KB Output is correct
6 Incorrect 1 ms 348 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 348 KB Output is correct
2 Correct 0 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 560 KB Output is correct
6 Incorrect 1 ms 348 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 348 KB Output is correct
2 Correct 0 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 560 KB Output is correct
6 Incorrect 1 ms 348 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 146 ms 12608 KB Output is correct
2 Correct 153 ms 12912 KB Output is correct
3 Correct 148 ms 12584 KB Output is correct
4 Correct 136 ms 19792 KB Output is correct
5 Correct 142 ms 13044 KB Output is correct
6 Correct 178 ms 19536 KB Output is correct
7 Correct 180 ms 19504 KB Output is correct
8 Correct 164 ms 19536 KB Output is correct
9 Correct 132 ms 18260 KB Output is correct
10 Correct 206 ms 19448 KB Output is correct
11 Correct 185 ms 19276 KB Output is correct
12 Correct 228 ms 19288 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 153 ms 13592 KB Output is correct
3 Correct 156 ms 13764 KB Output is correct
4 Correct 152 ms 13652 KB Output is correct
5 Incorrect 164 ms 14228 KB Output isn't correct
6 Halted 0 ms 0 KB -