#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = (int)2e5 + 5;
int n, l[N], r[N], q, nxt[N], mn[N][22], lg[N], t[8 * N], mod[8 * N], mx;
vector<int> vec;
bool intersect(const pair<int, int> &a, const pair<int, int> &b)
{
int L = max(a.fi, b.fi);
int R = min(a.sd, b.sd);
return R >= L;
}
int get(int l, int r)
{
int t = lg[r - l + 1];
return min(mn[l][t], mn[r - (1 << t) + 1][t]);
}
void push(int v, int tl, int tr)
{
if (tl == tr) return;
mod[v + v] = min(mod[v + v], mod[v]);
mod[v + v + 1] = min(mod[v + v + 1], mod[v]);
t[v + v] = min(t[v + v], mod[v]);
t[v + v + 1] = min(t[v + v + 1], mod[v]);
}
void build(int v, int tl, int tr)
{
if (tl == tr)
{
t[v] = n + 1;
mod[v] = n + 1;
return;
}
int m = (tl + tr) >> 1;
build(v + v, tl, m);
build(v + v + 1, m + 1, tr);
t[v] = min(t[v + v], t[v + v + 1]);
mod[v] = n + 1;
}
int get(int v, int tl, int tr, int l, int r)
{
push(v, tl, tr);
if (tl > tr || tl > r || tr < l) return n + 1;
if (tl >= l && tr <= r)
return t[v];
//push(v, tl, tr);
int m = (tl + tr) >> 1;
return min(get(v + v, tl, m, l, r), get(v + v + 1, m + 1, tr, l, r));
}
void upd(int v, int tl, int tr, int l, int r, int val)
{
push(v, tl, tr);
if (tl > tr || tl > r || tr < l) return;
if (tl >= l && tr <= r)
{
t[v] = min(t[v], val);
mod[v] = min(mod[v], val);
//push(v, tl, tr);
return;
}
int m = (tl + tr) >> 1;
//push(v, tl, tr);
upd(v + v, tl, m, l, r, val);
upd(v + v + 1, m + 1, tr, l, r, val);
t[v] = min(t[v + v], t[v + v + 1]);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
lg[1] = 0;
for(int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
for(int i = 1; i <= n; i++)
{
cin >> l[i] >> r[i];
vec.pb(l[i]);
vec.pb(r[i]);
}
sort(all(vec));
vec.erase(unique(all(vec)), vec.end());
for(int i = 1; i <= n; i++)
{
l[i] = lower_bound(all(vec), l[i]) - vec.begin(); l[i]++;
r[i] = lower_bound(all(vec), r[i]) - vec.begin(); r[i]++;
mx = max(mx, l[i]);
mx = max(mx, r[i]);
}
build(1, 1, mx);
for(int i = n; i >= 1; i--)
{
int val = get(1, 1, mx, l[i], r[i]);
nxt[i] = val;
mn[i][0] = nxt[i];
upd(1, 1, mx, l[i], r[i], i);
}
for(int i = 1; (1 << i) <= n; i++)
{
for(int j = 1; j + (1 << i) - 1 <= n; j++)
mn[j][i] = min(mn[j][i - 1], mn[j + (1 << (i - 1))][i - 1]);
}
for(int i = 1; i <= n; i++) nxt[i] = get(i, nxt[i] - 1);
vector< int > vc;
int i = 1;
while(i <= n)
{
vc.pb(i);
i = nxt[i];
}
cout << endl;
for(auto u : vc) cout << u << endl;
cout << endl;
cin >> q;
while(q--)
{
int le, ri;
cin >> le >> ri;
int ans = 0;
ans = 1; le = nxt[le];
if (le <= ri)
{
int skok1 = upper_bound(all(vc), ri) - vc.begin();
int skok2 = lower_bound(all(vc), le) - vc.begin();
ans += abs(skok2 - skok1);
//cout << upper_bound(all(vc), ri) - vc.begin() << ' ' << lower_bound(all(vc), le) - vc.begin() << endl;
}
// int i = le, ans = 0;
// while(i <= ri)
// {
// i = nxt[i];
// ans++;
// }
cout << ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
657 ms |
32096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
610 ms |
32996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
657 ms |
32096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
