oj.uz

Submission #1094721

# Submission time Handle Problem Language Result Execution time Memory
1094721 2024-09-30T11:00:29 Z crafticat Event Hopping (BOI22_events) C++17
10 / 100
 187 ms 17096 KB 
#include "bits/stdc++.h"

using namespace std;
template<typename T>
using V = vector<T>;
using vi = V<int>;
using pi = pair<int,int>;
#define f first
#define s second

#define F0R(i, n) for(int i = 0; i < n;i++)
#define FOR(i,a, n) for(int i = a; i < n;i++)
#define pb push_back
#define all(x) begin(x), end(x)
#define each(x, y) for(auto &x : y)
constexpr int INF = 1e9 + 2;

pi binarySearch(V<pair<pi,int>> &stack, pi point) {
    auto it = std::upper_bound(stack.begin(), stack.end(), make_pair(point,INF)); // Point to before or at point
    if (it == stack.begin()) return {0,0};
    it--;
    return {it - stack.begin() + 1, it->s};
}

int getImp(V<pair<pi, int>> &stack) {
    return (stack.empty() ? 0 : stack.back().s);
}

int main() {
    int n, q; cin >> n >> q;

    V<pair<pi, int>> edges;
    map<int, V<pair<pi, int>>> queries;
    V<int> ans(q, -1);

    F0R(i, n) {
        int a, b; cin >> a >> b;
        edges.pb({{b, a},i});
    }
    F0R(i, q) {
        int a, b; cin >> a >> b;
        a--;
        b--;

        if (edges[a].f.f == edges[b].f.f && a != b) ans[i] = 1;
        else queries[b].emplace_back(make_pair(edges[a].f.f,edges[a].f.s),i);
    }
    sort(all(edges));

    V<pair<pi,int>> stack; // Point, possible prefix
    // Self bug?

    each(edgeDATA, edges) {
        auto [edge, id] = edgeDATA;
        swap(edge.f, edge.s);
        pair<pi,int> last = {{-1, -1},-1};

        while (!stack.empty() && stack.back().f.f >= edge.f) {
            last = stack.back();
            stack.pop_back();
        }

        if (last.f.f != -1) stack.push_back(last);
        stack.emplace_back(make_pair(edge.s, edge.f),getImp(stack) + (last.f.f == -1 ? 1 : 0));

        each(starts, queries[id]) {
            auto data = binarySearch(stack, starts.f);
            if (getImp(stack) - data.s > 0) continue;
            if (starts.f.f > edge.s) continue;
            ans[starts.s] = stack.size() - data.f;
        }
    }

    F0R(i, q) {
        if (ans[i] == -1) cout << "impossible\n";
        else cout << ans[i] << "\n";
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 125 ms 15684 KB Output is correct
3 Correct 130 ms 16324 KB Output is correct
4 Correct 155 ms 16836 KB Output is correct
5 Correct 129 ms 16268 KB Output is correct
6 Correct 131 ms 16072 KB Output is correct
7 Correct 125 ms 16056 KB Output is correct
8 Correct 123 ms 16836 KB Output is correct
9 Correct 125 ms 16756 KB Output is correct
10 Correct 157 ms 17096 KB Output is correct
11 Correct 161 ms 16856 KB Output is correct
12 Correct 82 ms 15424 KB Output is correct

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 348 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 348 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 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 15696 KB Output is correct
2 Correct 141 ms 16268 KB Output is correct
3 Correct 154 ms 16840 KB Output is correct
4 Correct 131 ms 16836 KB Output is correct
5 Correct 171 ms 17092 KB Output is correct
6 Incorrect 187 ms 15812 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 125 ms 15684 KB Output is correct
3 Correct 130 ms 16324 KB Output is correct
4 Correct 155 ms 16836 KB Output is correct
5 Correct 129 ms 16268 KB Output is correct
6 Correct 131 ms 16072 KB Output is correct
7 Correct 125 ms 16056 KB Output is correct
8 Correct 123 ms 16836 KB Output is correct
9 Correct 125 ms 16756 KB Output is correct
10 Correct 157 ms 17096 KB Output is correct
11 Correct 161 ms 16856 KB Output is correct
12 Correct 82 ms 15424 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Incorrect 1 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -