#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
struct Tinter
{
ll l,r,id;
bool operator<(const Tinter&o)
{
return l<o.l;
}
}e[maxN];
ll lazy[8*maxN],st[8*maxN];
void down(ll id)
{
ll &x=lazy[id];
if(x!=-1)
{
st[id*2]=x;
lazy[id*2]=x;
st[id*2+1]=x;
lazy[id*2+1]=x;
x=-1;
}
}
ll n;
void update(ll i,ll j,ll val,ll id=1,ll l=1,ll r=2*n)
{
if(j<l||r<i) return;
if(i<=l&&r<=j)
{
st[id]=val;
lazy[id]=val;
return;
}
ll mid=l+r>>1;
down(id);
update(i,j,val,id*2,l,mid);
update(i,j,val,id*2+1,mid+1,r);
st[id]=min(st[id*2],st[id*2+1]);
}
ll get(ll i,ll j,ll id=1,ll l=1,ll r=2*n)
{
if(j<l||r<i) return n+1;
if(i<=l&&r<=j) return st[id];
ll mid=l+r>>1;
down(id);
return min(get(i,j,id*2,l,mid),get(i,j,id*2+1,mid+1,r));
}
ll r[maxN];
ll mn[maxN][19],nxt[maxN][19];
int log(ll x)
{
return 64 - __builtin_clzll(x) - 1;
}
ll g(ll i,ll j)
{
ll k=j-i+1;
k=log(k);
return min(mn[i][k],mn[j-(1<<k)+1][k]);
}
void solve()
{
vector<ll>vec;
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> e[i].l >> e[i].r;
vec.pb(e[i].l);
vec.pb(e[i].r);
e[i].id=i;
r[i]=n+1;
}
sort(vec.begin(),vec.end());
for(int i=1;i<=n;i++)
{
e[i].l=lower_bound(vec.begin(),vec.end(),e[i].l)-vec.begin()+1;
e[i].r=lower_bound(vec.begin(),vec.end(),e[i].r)-vec.begin()+1;
}
fill(st,st+8*maxN,n+1);
fill(lazy,lazy+8*maxN,-1);
for(int i=n;i>=1;i--)
{
r[i]=min(r[i],get(e[i].l,e[i].r));
update(e[i].l,e[i].r,i);
mn[i][0]=r[i];
//cout << r[i]<<' ';
}
for(int j=1;j<=18;j++)
{
for(int i=1;i<=n;i++)
{
if(i+(1<<j)-1>n) break;
mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
}
}
for(int i=1;i<=n;i++)
{
ll low=i,high=n;
while(low<=high)
{
ll mid=low+high>>1;
if(g(i,mid)>mid) low=mid+1;
else high=mid-1;
}
nxt[i][0]=low;
}
//cout << '\n';
nxt[n+1][0]=n+1;
for(int j=1;j<=18;j++)
{
for(int i=1;i<=n+1;i++)
{
nxt[i][j]=nxt[nxt[i][j-1]][j-1];
}
}
ll q;
cin >> q;
while(q--)
{
ll a,b;
cin >> a >> b;
ll ans=1;
for(int j=18;j>=0;j--)
{
if(nxt[a][j]<=b)
{
a=nxt[a][j];
ans+=1<<j;
}
}
cout << ans<<'\n';
}
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
Compilation message
Main.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
Main.cpp:44:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | ll mid=l+r>>1;
| ~^~
Main.cpp: In function 'll get(ll, ll, ll, ll, ll)':
Main.cpp:54:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | ll mid=l+r>>1;
| ~^~
Main.cpp: In function 'void solve()':
Main.cpp:110:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
110 | ll mid=low+high>>1;
| ~~~^~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
422 ms |
94996 KB |
Output is correct |
2 |
Correct |
437 ms |
93940 KB |
Output is correct |
3 |
Correct |
415 ms |
94096 KB |
Output is correct |
4 |
Correct |
431 ms |
95016 KB |
Output is correct |
5 |
Correct |
459 ms |
98096 KB |
Output is correct |
6 |
Correct |
207 ms |
91508 KB |
Output is correct |
7 |
Correct |
208 ms |
92540 KB |
Output is correct |
8 |
Correct |
224 ms |
93232 KB |
Output is correct |
9 |
Correct |
234 ms |
94872 KB |
Output is correct |
10 |
Correct |
227 ms |
92520 KB |
Output is correct |
11 |
Correct |
358 ms |
95980 KB |
Output is correct |
12 |
Correct |
319 ms |
91756 KB |
Output is correct |
13 |
Correct |
329 ms |
91588 KB |
Output is correct |
14 |
Correct |
347 ms |
96092 KB |
Output is correct |
15 |
Correct |
340 ms |
94192 KB |
Output is correct |
16 |
Correct |
10 ms |
25284 KB |
Output is correct |
17 |
Correct |
225 ms |
95956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
27348 KB |
Output is correct |
2 |
Correct |
19 ms |
27220 KB |
Output is correct |
3 |
Correct |
17 ms |
27196 KB |
Output is correct |
4 |
Correct |
18 ms |
27240 KB |
Output is correct |
5 |
Correct |
18 ms |
27132 KB |
Output is correct |
6 |
Correct |
16 ms |
27352 KB |
Output is correct |
7 |
Correct |
15 ms |
27248 KB |
Output is correct |
8 |
Correct |
17 ms |
27264 KB |
Output is correct |
9 |
Correct |
16 ms |
27220 KB |
Output is correct |
10 |
Correct |
15 ms |
27220 KB |
Output is correct |
11 |
Correct |
16 ms |
27352 KB |
Output is correct |
12 |
Correct |
15 ms |
27132 KB |
Output is correct |
13 |
Correct |
15 ms |
27220 KB |
Output is correct |
14 |
Correct |
17 ms |
27272 KB |
Output is correct |
15 |
Correct |
16 ms |
27268 KB |
Output is correct |
16 |
Correct |
10 ms |
25352 KB |
Output is correct |
17 |
Correct |
14 ms |
27244 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
27348 KB |
Output is correct |
2 |
Correct |
19 ms |
27220 KB |
Output is correct |
3 |
Correct |
17 ms |
27196 KB |
Output is correct |
4 |
Correct |
18 ms |
27240 KB |
Output is correct |
5 |
Correct |
18 ms |
27132 KB |
Output is correct |
6 |
Correct |
16 ms |
27352 KB |
Output is correct |
7 |
Correct |
15 ms |
27248 KB |
Output is correct |
8 |
Correct |
17 ms |
27264 KB |
Output is correct |
9 |
Correct |
16 ms |
27220 KB |
Output is correct |
10 |
Correct |
15 ms |
27220 KB |
Output is correct |
11 |
Correct |
16 ms |
27352 KB |
Output is correct |
12 |
Correct |
15 ms |
27132 KB |
Output is correct |
13 |
Correct |
15 ms |
27220 KB |
Output is correct |
14 |
Correct |
17 ms |
27272 KB |
Output is correct |
15 |
Correct |
16 ms |
27268 KB |
Output is correct |
16 |
Correct |
10 ms |
25352 KB |
Output is correct |
17 |
Correct |
14 ms |
27244 KB |
Output is correct |
18 |
Correct |
84 ms |
29952 KB |
Output is correct |
19 |
Correct |
79 ms |
29664 KB |
Output is correct |
20 |
Correct |
95 ms |
30016 KB |
Output is correct |
21 |
Correct |
83 ms |
29688 KB |
Output is correct |
22 |
Correct |
88 ms |
29744 KB |
Output is correct |
23 |
Correct |
76 ms |
29664 KB |
Output is correct |
24 |
Correct |
77 ms |
29900 KB |
Output is correct |
25 |
Correct |
75 ms |
29900 KB |
Output is correct |
26 |
Correct |
74 ms |
29844 KB |
Output is correct |
27 |
Correct |
72 ms |
29688 KB |
Output is correct |
28 |
Correct |
55 ms |
29264 KB |
Output is correct |
29 |
Correct |
57 ms |
29288 KB |
Output is correct |
30 |
Correct |
61 ms |
29332 KB |
Output is correct |
31 |
Correct |
66 ms |
29436 KB |
Output is correct |
32 |
Correct |
60 ms |
29392 KB |
Output is correct |
33 |
Correct |
10 ms |
25300 KB |
Output is correct |
34 |
Correct |
58 ms |
29536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
455 ms |
98272 KB |
Output is correct |
2 |
Correct |
432 ms |
96616 KB |
Output is correct |
3 |
Correct |
401 ms |
91784 KB |
Output is correct |
4 |
Correct |
400 ms |
91128 KB |
Output is correct |
5 |
Correct |
426 ms |
93260 KB |
Output is correct |
6 |
Correct |
205 ms |
91996 KB |
Output is correct |
7 |
Correct |
207 ms |
91264 KB |
Output is correct |
8 |
Correct |
219 ms |
91876 KB |
Output is correct |
9 |
Correct |
223 ms |
91180 KB |
Output is correct |
10 |
Correct |
242 ms |
96688 KB |
Output is correct |
11 |
Correct |
331 ms |
91120 KB |
Output is correct |
12 |
Correct |
347 ms |
97528 KB |
Output is correct |
13 |
Correct |
307 ms |
91096 KB |
Output is correct |
14 |
Correct |
350 ms |
93184 KB |
Output is correct |
15 |
Correct |
347 ms |
97132 KB |
Output is correct |
16 |
Correct |
10 ms |
25300 KB |
Output is correct |
17 |
Correct |
214 ms |
92860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
422 ms |
94996 KB |
Output is correct |
2 |
Correct |
437 ms |
93940 KB |
Output is correct |
3 |
Correct |
415 ms |
94096 KB |
Output is correct |
4 |
Correct |
431 ms |
95016 KB |
Output is correct |
5 |
Correct |
459 ms |
98096 KB |
Output is correct |
6 |
Correct |
207 ms |
91508 KB |
Output is correct |
7 |
Correct |
208 ms |
92540 KB |
Output is correct |
8 |
Correct |
224 ms |
93232 KB |
Output is correct |
9 |
Correct |
234 ms |
94872 KB |
Output is correct |
10 |
Correct |
227 ms |
92520 KB |
Output is correct |
11 |
Correct |
358 ms |
95980 KB |
Output is correct |
12 |
Correct |
319 ms |
91756 KB |
Output is correct |
13 |
Correct |
329 ms |
91588 KB |
Output is correct |
14 |
Correct |
347 ms |
96092 KB |
Output is correct |
15 |
Correct |
340 ms |
94192 KB |
Output is correct |
16 |
Correct |
10 ms |
25284 KB |
Output is correct |
17 |
Correct |
225 ms |
95956 KB |
Output is correct |
18 |
Correct |
18 ms |
27348 KB |
Output is correct |
19 |
Correct |
19 ms |
27220 KB |
Output is correct |
20 |
Correct |
17 ms |
27196 KB |
Output is correct |
21 |
Correct |
18 ms |
27240 KB |
Output is correct |
22 |
Correct |
18 ms |
27132 KB |
Output is correct |
23 |
Correct |
16 ms |
27352 KB |
Output is correct |
24 |
Correct |
15 ms |
27248 KB |
Output is correct |
25 |
Correct |
17 ms |
27264 KB |
Output is correct |
26 |
Correct |
16 ms |
27220 KB |
Output is correct |
27 |
Correct |
15 ms |
27220 KB |
Output is correct |
28 |
Correct |
16 ms |
27352 KB |
Output is correct |
29 |
Correct |
15 ms |
27132 KB |
Output is correct |
30 |
Correct |
15 ms |
27220 KB |
Output is correct |
31 |
Correct |
17 ms |
27272 KB |
Output is correct |
32 |
Correct |
16 ms |
27268 KB |
Output is correct |
33 |
Correct |
10 ms |
25352 KB |
Output is correct |
34 |
Correct |
14 ms |
27244 KB |
Output is correct |
35 |
Correct |
84 ms |
29952 KB |
Output is correct |
36 |
Correct |
79 ms |
29664 KB |
Output is correct |
37 |
Correct |
95 ms |
30016 KB |
Output is correct |
38 |
Correct |
83 ms |
29688 KB |
Output is correct |
39 |
Correct |
88 ms |
29744 KB |
Output is correct |
40 |
Correct |
76 ms |
29664 KB |
Output is correct |
41 |
Correct |
77 ms |
29900 KB |
Output is correct |
42 |
Correct |
75 ms |
29900 KB |
Output is correct |
43 |
Correct |
74 ms |
29844 KB |
Output is correct |
44 |
Correct |
72 ms |
29688 KB |
Output is correct |
45 |
Correct |
55 ms |
29264 KB |
Output is correct |
46 |
Correct |
57 ms |
29288 KB |
Output is correct |
47 |
Correct |
61 ms |
29332 KB |
Output is correct |
48 |
Correct |
66 ms |
29436 KB |
Output is correct |
49 |
Correct |
60 ms |
29392 KB |
Output is correct |
50 |
Correct |
10 ms |
25300 KB |
Output is correct |
51 |
Correct |
58 ms |
29536 KB |
Output is correct |
52 |
Correct |
455 ms |
98272 KB |
Output is correct |
53 |
Correct |
432 ms |
96616 KB |
Output is correct |
54 |
Correct |
401 ms |
91784 KB |
Output is correct |
55 |
Correct |
400 ms |
91128 KB |
Output is correct |
56 |
Correct |
426 ms |
93260 KB |
Output is correct |
57 |
Correct |
205 ms |
91996 KB |
Output is correct |
58 |
Correct |
207 ms |
91264 KB |
Output is correct |
59 |
Correct |
219 ms |
91876 KB |
Output is correct |
60 |
Correct |
223 ms |
91180 KB |
Output is correct |
61 |
Correct |
242 ms |
96688 KB |
Output is correct |
62 |
Correct |
331 ms |
91120 KB |
Output is correct |
63 |
Correct |
347 ms |
97528 KB |
Output is correct |
64 |
Correct |
307 ms |
91096 KB |
Output is correct |
65 |
Correct |
350 ms |
93184 KB |
Output is correct |
66 |
Correct |
347 ms |
97132 KB |
Output is correct |
67 |
Correct |
10 ms |
25300 KB |
Output is correct |
68 |
Correct |
214 ms |
92860 KB |
Output is correct |
69 |
Correct |
682 ms |
96720 KB |
Output is correct |
70 |
Correct |
641 ms |
100468 KB |
Output is correct |
71 |
Correct |
592 ms |
94772 KB |
Output is correct |
72 |
Correct |
617 ms |
98520 KB |
Output is correct |
73 |
Correct |
729 ms |
97232 KB |
Output is correct |
74 |
Correct |
454 ms |
100924 KB |
Output is correct |
75 |
Correct |
396 ms |
95676 KB |
Output is correct |
76 |
Correct |
410 ms |
101548 KB |
Output is correct |
77 |
Correct |
419 ms |
95380 KB |
Output is correct |
78 |
Correct |
411 ms |
96460 KB |
Output is correct |
79 |
Correct |
429 ms |
100056 KB |
Output is correct |
80 |
Correct |
377 ms |
94484 KB |
Output is correct |
81 |
Correct |
387 ms |
94096 KB |
Output is correct |
82 |
Correct |
433 ms |
97972 KB |
Output is correct |
83 |
Correct |
409 ms |
94584 KB |
Output is correct |
84 |
Correct |
10 ms |
25300 KB |
Output is correct |
85 |
Correct |
273 ms |
95424 KB |
Output is correct |