#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 100005;
const int inf = 1e9;
int n, q;
pair<int, int> intervals[mx];
int ans[mx];
struct qd {
set<pair<int, pair<int, int>>> qs;
int cost;
qd() {
cost = 0;
}
void ins(pair<int, int> p) {
qs.insert({p.first, {0, p.second}});
}
void merge(qd & oth) {
int delta = oth.cost - cost;
for(auto p : oth.qs) {
qs.insert({p.first, {p.second.first + delta, p.second.second}});
}
}
void sync(int i) {
auto lim = qs.lower_bound({i + 1, {0, 0}});
for(auto it = qs.begin(); it != lim; it = qs.erase(it)) {
ans[it->second.second] = cost + it->second.first;
}
}
};
qd data0[mx];
struct st {
pair<int, int> best;
st * l;
st * r;
int size;
st() {}
st(int sz, int i) {
size = sz;
if(size > 1) {
l = new st(size/2, i);
r = new st((size + 1)/2, i + (size/2));
best = max(l->best, r->best);
} else {
best = {intervals[i].second, i};
}
}
pair<int, int> get(int s, int e) { /* [l, r) */
s = max(0, s);
e = min(e, size);
if(s == 0 && e == size) return best;
pair<int, int> res = {0, 0};
if(s < l->size) res = max(res, l->get(s, e));
if(e > l->size) res = max(res, r->get(s - l->size, e - l->size));
return res;
}
};
st tree;
int get_idx(int i) {
int a = 0;
for(int delta = (1<<19); delta >= 1; delta >>= 1) {
int tmp = a + delta;
if(tmp >= n) continue;
if(intervals[tmp].first <= i) a = tmp;
}
return a;
}
main() {
for(int i = 0; i < mx; i++) ans[i] = -1;
cin >> n >> q;
vector<pair<int, int>> orig(n);
for(int i = 0; i < n; i++) {
int s, e; cin >> s >> e;
orig[i] = {s, e};
intervals[i] = {inf - e, inf - s};
}
vector<pair<pair<int, int>, int>> order(n);
for(int i = 0; i < n; i++) {
order[i] = {{intervals[i].first, -intervals[i].second}, i};
}
sort(order.begin(), order.end());
vector<int> pos(n);
for(int i = 0; i < n; i++) {
pos[order[i].second] = i;
}
for(int i = 0; i < q; i++) {
int s, e; cin >> e >> s;
if(s == e) {
ans[i] = 0;
continue;
}
if(orig[e - 1].second > orig[s - 1].second) continue;
data0[pos[s - 1]].ins({intervals[e - 1].first, i});
}
vector<pair<int, int>> tmp(n);
for(int i = 0; i < n; i++) {
tmp[i] = intervals[order[i].second];
}
for(int i = 0; i < n; i++) {
intervals[i] = tmp[i];
}
tree = st(n, 0);
for(int i = 0; i < n; i++) {
int r = intervals[i].second;
int dst_int = get_idx(r);
data0[i].cost++;
data0[i].sync(r);
if(dst_int == i) continue;
pair<int, int> next_best = tree.get(i + 1, dst_int + 1);
int nidx = next_best.second;
if(data0[i].qs.size() > data0[nidx].qs.size()) swap(data0[i], data0[nidx]);
data0[nidx].merge(data0[i]);
}
for(int i = 0; i < q; i++) {
if(ans[i] == -1) cout << "impossible" << endl;
else cout << ans[i] << endl;
}
}
Compilation message
events.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
68 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6100 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
6100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6100 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
6100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6100 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
6100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
328 ms |
26236 KB |
Output is correct |
| 2 |
Correct |
331 ms |
32564 KB |
Output is correct |
| 3 |
Correct |
326 ms |
32568 KB |
Output is correct |
| 4 |
Correct |
288 ms |
26828 KB |
Output is correct |
| 5 |
Correct |
332 ms |
25428 KB |
Output is correct |
| 6 |
Incorrect |
317 ms |
24924 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
