oj.uz

Submission #1094732

# Submission time Handle Problem Language Result Execution time Memory
1094732 2024-09-30T11:30:01 Z crafticat Event Hopping (BOI22_events) C++17
10 / 100
 180 ms 17448 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--;
    int b = 0;
    return {it - stack.begin() + 1 + b, 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 if (a != b && edges[b].f.f >= edges[a].f.f && edges[b].f.s <= edges[a].f.f) 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 0 ms 344 KB Output is correct
2 Correct 129 ms 14404 KB Output is correct
3 Correct 136 ms 15044 KB Output is correct
4 Correct 164 ms 15560 KB Output is correct
5 Correct 141 ms 14788 KB Output is correct
6 Correct 136 ms 14788 KB Output is correct
7 Correct 152 ms 14676 KB Output is correct
8 Correct 163 ms 15512 KB Output is correct
9 Correct 128 ms 16836 KB Output is correct
10 Correct 177 ms 17448 KB Output is correct
11 Correct 166 ms 16584 KB Output is correct
12 Correct 87 ms 15428 KB Output is correct

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 344 KB Output is correct
6 Incorrect 2 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 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 344 KB Output is correct
6 Incorrect 2 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 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 344 KB Output is correct
6 Incorrect 2 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 140 ms 14444 KB Output is correct
2 Correct 141 ms 15052 KB Output is correct
3 Correct 172 ms 15484 KB Output is correct
4 Correct 133 ms 15416 KB Output is correct
5 Correct 172 ms 15816 KB Output is correct
6 Incorrect 180 ms 14376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 129 ms 14404 KB Output is correct
3 Correct 136 ms 15044 KB Output is correct
4 Correct 164 ms 15560 KB Output is correct
5 Correct 141 ms 14788 KB Output is correct
6 Correct 136 ms 14788 KB Output is correct
7 Correct 152 ms 14676 KB Output is correct
8 Correct 163 ms 15512 KB Output is correct
9 Correct 128 ms 16836 KB Output is correct
10 Correct 177 ms 17448 KB Output is correct
11 Correct 166 ms 16584 KB Output is correct
12 Correct 87 ms 15428 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 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 344 KB Output is correct
18 Incorrect 2 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -