#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;
if (it->first != point) b++;
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 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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
132 ms |
15652 KB |
Output is correct |
3 |
Correct |
129 ms |
16224 KB |
Output is correct |
4 |
Correct |
153 ms |
16840 KB |
Output is correct |
5 |
Incorrect |
132 ms |
16068 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
- |
# |
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 |
- |
# |
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 |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
136 ms |
15680 KB |
Output is correct |
2 |
Correct |
136 ms |
16368 KB |
Output is correct |
3 |
Correct |
150 ms |
16868 KB |
Output is correct |
4 |
Correct |
131 ms |
16840 KB |
Output is correct |
5 |
Correct |
162 ms |
17096 KB |
Output is correct |
6 |
Incorrect |
168 ms |
15816 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
132 ms |
15652 KB |
Output is correct |
3 |
Correct |
129 ms |
16224 KB |
Output is correct |
4 |
Correct |
153 ms |
16840 KB |
Output is correct |
5 |
Incorrect |
132 ms |
16068 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |