# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1077538 |
2024-08-27T07:55:46 Z |
LIF |
Event Hopping (BOI22_events) |
C++14 |
|
255 ms |
20824 KB |
#include<bits/stdc++.h>
using namespace std;
int n,q,l[500005],r[500005],go[500005][30],pos[500005];
struct mn
{
int val;
int id;
}minn[800005];
struct nod
{
int ll;
int rr;
int id;
}node[500005];
bool cmp(nod x,nod y)
{
if(x.rr == y.rr)return x.ll < y.ll;
else return x.rr < y.rr;
}
int read()
{
int x=0,f=1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x<<3) + (x<<1) + (ch-'0');
ch = getchar();
}
return x*f;
}
void pushup(int rt)
{
if(minn[rt<<1].val < minn[rt<<1|1].val)
{
minn[rt].val = minn[rt<<1].val;
minn[rt].id = minn[rt<<1].id;
}
else
{
minn[rt].val = minn[rt<<1|1].val;
minn[rt].id = minn[rt<<1|1].id;
}
return;
}
pair<int,int> query(int l,int r,int queryl,int queryr,int rt)
{
if(queryl <= l && r <= queryr)
{
return make_pair(minn[rt].val,minn[rt].id);
}
int mid = (l+r)>>1;
pair<int,int> fir = make_pair(2e9,-1);
if(mid >= queryl)
{
auto pp = query(l,mid,queryl,queryr,rt<<1);
if(pp.first < fir.first)fir = pp;
}
if(mid + 1 <= queryr)
{
auto pp = query(mid+1,r,queryl,queryr,rt<<1|1);
if(pp.first < fir.first)fir = pp;
}
return fir;
}
void build(int l,int r,int rt)
{
if(l == r)
{
minn[rt].val = node[l].ll;
minn[rt].id = l;
return;
}
int mid = (l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
return;
}
int main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
{
l[i] = read();r[i] = read();
nod temp = nod{l[i],r[i],i};
node[i] = temp;
}
sort(node+1,node+n+1,cmp);
build(1,n,1);
for(int i=1;i<=n;i++)
{
go[i][0] = -1;
int ll = 1,rr = i-1,last = -1;
while (ll<=rr)
{
int mid = (ll+rr)>>1;
if(node[mid].rr >= node[i].ll)
{
last = mid;
rr = mid - 1;
}
else ll = mid + 1;
}
if(last <= 0)go[i][0] = -1;
else
{
auto pp = query(1,n,last,i-1,1);
go[i][0] = pp.second;
}
}
for(int i=1;i<=n;i++)
{
pos[node[i].id] = i;
}
for(int i=1;i<=20;i++)
{
for(int j=1;j<=n;j++)
{
if(go[j][i-1] == -1)
{
go[j][i] = -1;
continue;
}
go[j][i] = go[go[j][i-1]][i-1];
}
}
// for(int i=1;i<=n;i++)
// {
// cout<<node[i].ll<<" "<<node[i].rr<<endl;
// }
// for(int i=1;i<=n;i++)
// {
// cout<<go[i][0]<<" ";
// }
// cout<<endl;
// cout<<endl;
while(q--)
{
int s,e;
cin>>s>>e;
if(e == s)
{
cout<<"0"<<endl;
continue;
}
if(l[e] <= r[s] && r[s] <= r[e])
{
cout<<"1"<<endl;
continue;
}
int now = pos[e];
int ans = 0;
bool can = true;
for(int i=20;i>=0;i--)
{
int target = go[now][i];
if(target == -1)continue;
if(node[target].ll > r[s])
{
//cout<<"now: "<<now<<" target: "<<target<<endl;
now = target;
ans += pow(2,i);
}
}
if(go[now][0] == -1)
{
can = false;
}
else
{
now = go[now][0];
ans++;
}
//cout<<"last: "<<now<<endl;
int ll = node[now].ll;
int rr = node[now].rr;
if(ll <= r[s] && r[s] <= rr)cout<<ans+1<<endl;
else cout<<"impossible"<<endl;
}
return 0;
}
Compilation message
events.cpp: In function 'int main()':
events.cpp:158:14: warning: variable 'can' set but not used [-Wunused-but-set-variable]
158 | bool can = true;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
194 ms |
19288 KB |
Output is correct |
3 |
Correct |
194 ms |
20304 KB |
Output is correct |
4 |
Correct |
232 ms |
20296 KB |
Output is correct |
5 |
Correct |
206 ms |
20176 KB |
Output is correct |
6 |
Correct |
240 ms |
20304 KB |
Output is correct |
7 |
Correct |
195 ms |
20292 KB |
Output is correct |
8 |
Correct |
173 ms |
20564 KB |
Output is correct |
9 |
Correct |
224 ms |
20768 KB |
Output is correct |
10 |
Correct |
234 ms |
20568 KB |
Output is correct |
11 |
Correct |
211 ms |
20568 KB |
Output is correct |
12 |
Correct |
162 ms |
20048 KB |
Output is correct |
# |
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 |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
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 |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
856 KB |
Output is correct |
15 |
Correct |
1 ms |
600 KB |
Output is correct |
16 |
Correct |
1 ms |
600 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
150 ms |
2488 KB |
Output is correct |
20 |
Correct |
142 ms |
2392 KB |
Output is correct |
21 |
Correct |
196 ms |
2812 KB |
Output is correct |
22 |
Correct |
135 ms |
2896 KB |
Output is correct |
23 |
Correct |
147 ms |
2964 KB |
Output is correct |
24 |
Correct |
143 ms |
2896 KB |
Output is correct |
25 |
Correct |
142 ms |
2388 KB |
Output is correct |
# |
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 |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
496 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
39 ms |
17748 KB |
Output is correct |
20 |
Correct |
36 ms |
17236 KB |
Output is correct |
21 |
Correct |
45 ms |
17668 KB |
Output is correct |
22 |
Correct |
42 ms |
17864 KB |
Output is correct |
23 |
Correct |
50 ms |
17748 KB |
Output is correct |
24 |
Correct |
44 ms |
17812 KB |
Output is correct |
25 |
Correct |
31 ms |
17144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
216 ms |
19284 KB |
Output is correct |
2 |
Correct |
190 ms |
20304 KB |
Output is correct |
3 |
Correct |
195 ms |
20112 KB |
Output is correct |
4 |
Correct |
175 ms |
20824 KB |
Output is correct |
5 |
Correct |
224 ms |
20560 KB |
Output is correct |
6 |
Correct |
212 ms |
20276 KB |
Output is correct |
7 |
Correct |
235 ms |
20244 KB |
Output is correct |
8 |
Correct |
218 ms |
20560 KB |
Output is correct |
9 |
Correct |
40 ms |
18516 KB |
Output is correct |
10 |
Correct |
193 ms |
20052 KB |
Output is correct |
11 |
Correct |
189 ms |
19672 KB |
Output is correct |
12 |
Correct |
206 ms |
19892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
194 ms |
19288 KB |
Output is correct |
3 |
Correct |
194 ms |
20304 KB |
Output is correct |
4 |
Correct |
232 ms |
20296 KB |
Output is correct |
5 |
Correct |
206 ms |
20176 KB |
Output is correct |
6 |
Correct |
240 ms |
20304 KB |
Output is correct |
7 |
Correct |
195 ms |
20292 KB |
Output is correct |
8 |
Correct |
173 ms |
20564 KB |
Output is correct |
9 |
Correct |
224 ms |
20768 KB |
Output is correct |
10 |
Correct |
234 ms |
20568 KB |
Output is correct |
11 |
Correct |
211 ms |
20568 KB |
Output is correct |
12 |
Correct |
162 ms |
20048 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
856 KB |
Output is correct |
27 |
Correct |
1 ms |
600 KB |
Output is correct |
28 |
Correct |
1 ms |
600 KB |
Output is correct |
29 |
Correct |
1 ms |
604 KB |
Output is correct |
30 |
Correct |
1 ms |
604 KB |
Output is correct |
31 |
Correct |
150 ms |
2488 KB |
Output is correct |
32 |
Correct |
142 ms |
2392 KB |
Output is correct |
33 |
Correct |
196 ms |
2812 KB |
Output is correct |
34 |
Correct |
135 ms |
2896 KB |
Output is correct |
35 |
Correct |
147 ms |
2964 KB |
Output is correct |
36 |
Correct |
143 ms |
2896 KB |
Output is correct |
37 |
Correct |
142 ms |
2388 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
604 KB |
Output is correct |
41 |
Correct |
1 ms |
604 KB |
Output is correct |
42 |
Correct |
1 ms |
604 KB |
Output is correct |
43 |
Correct |
1 ms |
496 KB |
Output is correct |
44 |
Correct |
1 ms |
604 KB |
Output is correct |
45 |
Correct |
1 ms |
604 KB |
Output is correct |
46 |
Correct |
1 ms |
604 KB |
Output is correct |
47 |
Correct |
39 ms |
17748 KB |
Output is correct |
48 |
Correct |
36 ms |
17236 KB |
Output is correct |
49 |
Correct |
45 ms |
17668 KB |
Output is correct |
50 |
Correct |
42 ms |
17864 KB |
Output is correct |
51 |
Correct |
50 ms |
17748 KB |
Output is correct |
52 |
Correct |
44 ms |
17812 KB |
Output is correct |
53 |
Correct |
31 ms |
17144 KB |
Output is correct |
54 |
Correct |
216 ms |
19284 KB |
Output is correct |
55 |
Correct |
190 ms |
20304 KB |
Output is correct |
56 |
Correct |
195 ms |
20112 KB |
Output is correct |
57 |
Correct |
175 ms |
20824 KB |
Output is correct |
58 |
Correct |
224 ms |
20560 KB |
Output is correct |
59 |
Correct |
212 ms |
20276 KB |
Output is correct |
60 |
Correct |
235 ms |
20244 KB |
Output is correct |
61 |
Correct |
218 ms |
20560 KB |
Output is correct |
62 |
Correct |
40 ms |
18516 KB |
Output is correct |
63 |
Correct |
193 ms |
20052 KB |
Output is correct |
64 |
Correct |
189 ms |
19672 KB |
Output is correct |
65 |
Correct |
206 ms |
19892 KB |
Output is correct |
66 |
Correct |
0 ms |
344 KB |
Output is correct |
67 |
Correct |
188 ms |
20296 KB |
Output is correct |
68 |
Correct |
193 ms |
20184 KB |
Output is correct |
69 |
Correct |
210 ms |
20328 KB |
Output is correct |
70 |
Correct |
194 ms |
20204 KB |
Output is correct |
71 |
Correct |
191 ms |
20292 KB |
Output is correct |
72 |
Correct |
205 ms |
20304 KB |
Output is correct |
73 |
Correct |
204 ms |
20560 KB |
Output is correct |
74 |
Correct |
167 ms |
20560 KB |
Output is correct |
75 |
Correct |
214 ms |
20564 KB |
Output is correct |
76 |
Correct |
200 ms |
20560 KB |
Output is correct |
77 |
Correct |
178 ms |
20056 KB |
Output is correct |
78 |
Correct |
1 ms |
344 KB |
Output is correct |
79 |
Correct |
1 ms |
492 KB |
Output is correct |
80 |
Correct |
1 ms |
600 KB |
Output is correct |
81 |
Correct |
1 ms |
604 KB |
Output is correct |
82 |
Correct |
1 ms |
604 KB |
Output is correct |
83 |
Correct |
1 ms |
604 KB |
Output is correct |
84 |
Correct |
1 ms |
600 KB |
Output is correct |
85 |
Correct |
1 ms |
604 KB |
Output is correct |
86 |
Correct |
160 ms |
2900 KB |
Output is correct |
87 |
Correct |
150 ms |
2644 KB |
Output is correct |
88 |
Correct |
148 ms |
2808 KB |
Output is correct |
89 |
Correct |
142 ms |
2900 KB |
Output is correct |
90 |
Correct |
137 ms |
2900 KB |
Output is correct |
91 |
Correct |
144 ms |
2896 KB |
Output is correct |
92 |
Correct |
137 ms |
2376 KB |
Output is correct |
93 |
Correct |
38 ms |
18516 KB |
Output is correct |
94 |
Correct |
34 ms |
17744 KB |
Output is correct |
95 |
Correct |
45 ms |
18452 KB |
Output is correct |
96 |
Correct |
39 ms |
18456 KB |
Output is correct |
97 |
Correct |
41 ms |
18524 KB |
Output is correct |
98 |
Correct |
44 ms |
18536 KB |
Output is correct |
99 |
Correct |
30 ms |
17636 KB |
Output is correct |
100 |
Correct |
242 ms |
20436 KB |
Output is correct |
101 |
Correct |
209 ms |
20308 KB |
Output is correct |
102 |
Correct |
199 ms |
20400 KB |
Output is correct |
103 |
Correct |
189 ms |
20060 KB |
Output is correct |
104 |
Correct |
190 ms |
19672 KB |
Output is correct |
105 |
Correct |
201 ms |
20124 KB |
Output is correct |
106 |
Correct |
205 ms |
19536 KB |
Output is correct |
107 |
Correct |
214 ms |
19540 KB |
Output is correct |
108 |
Correct |
215 ms |
20304 KB |
Output is correct |
109 |
Correct |
195 ms |
20308 KB |
Output is correct |
110 |
Correct |
210 ms |
20308 KB |
Output is correct |
111 |
Correct |
255 ms |
20284 KB |
Output is correct |