#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
struct LazySegmentTree {
vector <int> lzy, f;
int n;
LazySegmentTree(int _n) {
n = _n;
lzy.resize(n * 4 + 5, -1);
f.resize(n * 4 + 5, 0);
}
int merge(int x, int y) { return max(x, y); }
void push(int x, int l, int r) {
if (lzy[x] != -1) return;
int val = lzy[x];
f[x << 1] = val;
lzy[x << 1] = val;
f[x << 1 | 1] = val;
lzy[x << 1 | 1] = val;
lzy[x] = -1;
return;
}
void upd(int x, int l, int r, int u, int v, int val) {
if (l > v || r < u) return;
if (u <= l && r <= v) {
f[x] = val;
lzy[x] = val;
return;
}
int m = (l + r) / 2;
push(x, l, r);
upd(x << 1, l, m, u, v, val);
upd(x << 1 | 1, m + 1, r, u, v, val);
f[x] = merge(f[x << 1], f[x << 1 | 1]);
}
void upd(int l, int r, int val) { upd(1, 1, n, l, r, val); }
int qry(int x, int l, int r, int u, int v) {
if (l > v || r < u) return 0;
if (u <= l && r <= v) return f[x];
int m = (l + r) / 2;
push(x, l, r);
int ql = qry(x << 1, l, m, u, v);
int qr = qry(x << 1 | 1, m + 1, r, u, v);
return merge(ql, qr);
}
int qry(int l, int r) { return qry(1, 1, n, l, r); }
};
const int LG = 18;
signed main() {
cin.tie(0) -> sync_with_stdio(0);
#ifdef JASPER
freopen("in1", "r", stdin);
#endif
vector <int> vals;
int n, q;
cin >> n;
vector <pair <int, int>> segs(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> segs[i].first >> segs[i].second;
vals.push_back(segs[i].first);
vals.push_back(segs[i].second);
}
sort(vals.begin(), vals.end());
vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
for (int i = 1; i <= n; ++i) {
segs[i].first = (int) (lower_bound(vals.begin(), vals.end(), segs[i].first) - vals.begin() + 1);
segs[i].second = (int) (lower_bound(vals.begin(), vals.end(), segs[i].second) - vals.begin() + 1);
debug(segs[i]);
}
LazySegmentTree st((int) vals.size());
vector <int> nxt(n + 1, 0);
int j = 1;
for (int i = 1; i <= n; ++i) {
while (j <= n && st.qry(segs[j].first, segs[j].second) == 0) {
st.upd(segs[j].first, segs[j].second, 1);
++j;
}
nxt[i] = j;
st.upd(segs[i].first, segs[i].second, 0);
}
nxt[n] = n + 1;
vector <vector <int>> up(LG, vector <int> (n + 1, 0));
// up(i, j) = nxt(..nxt(i)), use nxt() j times
for (int i = 1; i <= n; ++i)
up[0][i] = nxt[i];
for (int i = 1; i <= n; ++i)
for (int j = 1; j < LG; ++j)
up[j][i] = up[j - 1][up[j - 1][i]];
cin >> q;
for (int _q = 1; _q <= q; ++_q) {
int l, r;
cin >> l >> r;
int res = 1;
while (nxt[l] <= r) {
++res;
l = nxt[l];
}
cout << res << "\n";
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:9:20: warning: statement has no effect [-Wunused-value]
9 | #define debug(...) 166
| ^~~
Main.cpp:91:9: note: in expansion of macro 'debug'
91 | debug(segs[i]);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
332 ms |
33480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
1372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
1372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
384 ms |
35060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
332 ms |
33480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
