#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1<<17;
const int MAXP = 19;
int droite[MAXN];
int gauche[MAXN];
struct inter
{
int deb,fin;
bool operator == (const inter & autre) const
{
return deb == autre.deb && fin == autre.fin;
}
};
inter vide = {-1 , -1};
struct prQ
{
int val , pos;
};
inter union_inter(inter a , inter b)
{
if (a == vide) return b;
if (b == vide) return a;
return {min(a.deb , b.deb) , max(a.fin , b.fin)};
}
inter intervalles[MAXN * 2][MAXP];
void init()
{
for (int i = 0 ; i < MAXN * 2 ; i++)
{
for (int j = 0 ; j < MAXP ; j++)
{
intervalles[i][j] = vide;
}
}
}
void remplir_etage(int et)
{
for (int i = MAXN- 1 ; i > 0 ; i--)
{
intervalles[i][et] = union_inter(intervalles[i * 2][et] , intervalles[i * 2 + 1][et]);
}
}
inter maxi(int deb , int fin , int et)
{
deb += MAXN;
fin += MAXN;
inter rep = vide;
while (deb <= fin)
{
if (deb % 2 == 1)
{
rep = union_inter(rep , intervalles[deb][et]);
deb++;
}
if (fin % 2 == 0)
{
rep = union_inter(rep , intervalles[fin][et]);
fin--;
}
deb/=2;
fin/=2;
}
return rep;
}
bool contient (inter a , int b)
{
return a.deb <= b && a.fin >= b;
}
int main()
{
init();
int N , K;
cin >> N >> K;
int M;
cin >> M;
for (int i = 0 ; i < MAXN ; i++)
{
droite[i] = -1;
gauche[i] = -1;
}
for (int i = 0 ; i < M ; i++)
{
int a,b;
cin >> a >> b;
a--; b--;
if (a < b)
{
droite[a] = max(droite[a] , b);
}
else
{
if (gauche[a] == -1) gauche[a] = b;
else gauche[a] = min(gauche[a] , b);
}
}
deque<prQ> Q;
for (int i = 0 ; i < N ; i++)
{
if (droite[i] != -1)
{
while (!Q.empty() && Q.front().val <= droite[i])
Q.pop_front();
Q.push_front({droite[i] , i});
}
while (!Q.empty() && Q.back().pos + K <= i)
Q.pop_back();
if (Q.empty())
intervalles[i + MAXN][0].fin = i;
else
intervalles[i + MAXN][0].fin = max(i , Q.back().val);
}
Q.clear();
for (int i = N - 1 ; i >= 0 ; i--)
{
if (gauche[i] != -1)
{
while (!Q.empty() && Q.front().val >= gauche[i])
Q.pop_front();
Q.push_front({gauche[i] , i});
}
while (!Q.empty() && Q.back().pos - K >= i)
Q.pop_back();
if (Q.empty())
intervalles[i + MAXN][0].deb = i;
else
{
// cout<<"A"<<i<<" "<<Q.back().pos<<endl;
intervalles[i + MAXN][0].deb = min(i , Q.back().val);
}
}
/*for (int i = 0 ; i < N ; i++)
{
cout<<intervalles[i + MAXN][0].deb<<" "<<intervalles[i + MAXN][0].fin<<endl;
}*/
remplir_etage(0);
for (int iP = 1 ; iP < MAXP ; iP++)
{
for (int i = 0 ; i < N ; i++)
{
intervalles[i + MAXN][iP] = maxi(intervalles[i + MAXN][iP - 1].deb , intervalles[i + MAXN][iP - 1].fin , iP - 1);
}
remplir_etage(iP);
}
int nbQ;
cin >> nbQ;
for (int i = 0 ; i < nbQ ; i++)
{
int s,t;
cin >> s >> t;
s--; t--;
inter tout = maxi(s , s , MAXP - 1);
if (!contient(tout , t)) {cout<<-1<<endl; continue;}
if (s == t) {cout<<0<<endl; continue;}
int rep = 0;
inter actu = {s , s};
for (int iP = MAXP - 1 ; iP >= 0 ; iP--)
{
inter in = maxi(actu.deb , actu.fin , iP);
if (!contient(in , t))
{
actu = in;
rep += 1<<iP;
}
}
cout<<rep + 1<<endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
52 ms |
40296 KB |
Output is correct |
2 |
Correct |
51 ms |
40300 KB |
Output is correct |
3 |
Correct |
49 ms |
40184 KB |
Output is correct |
4 |
Correct |
48 ms |
40276 KB |
Output is correct |
5 |
Correct |
50 ms |
40296 KB |
Output is correct |
6 |
Correct |
48 ms |
40256 KB |
Output is correct |
7 |
Correct |
50 ms |
40204 KB |
Output is correct |
8 |
Correct |
50 ms |
40296 KB |
Output is correct |
9 |
Correct |
51 ms |
40320 KB |
Output is correct |
10 |
Correct |
54 ms |
40180 KB |
Output is correct |
11 |
Correct |
50 ms |
40200 KB |
Output is correct |
12 |
Correct |
51 ms |
40244 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
52 ms |
40296 KB |
Output is correct |
2 |
Correct |
51 ms |
40300 KB |
Output is correct |
3 |
Correct |
49 ms |
40184 KB |
Output is correct |
4 |
Correct |
48 ms |
40276 KB |
Output is correct |
5 |
Correct |
50 ms |
40296 KB |
Output is correct |
6 |
Correct |
48 ms |
40256 KB |
Output is correct |
7 |
Correct |
50 ms |
40204 KB |
Output is correct |
8 |
Correct |
50 ms |
40296 KB |
Output is correct |
9 |
Correct |
51 ms |
40320 KB |
Output is correct |
10 |
Correct |
54 ms |
40180 KB |
Output is correct |
11 |
Correct |
50 ms |
40200 KB |
Output is correct |
12 |
Correct |
51 ms |
40244 KB |
Output is correct |
13 |
Correct |
62 ms |
40328 KB |
Output is correct |
14 |
Correct |
56 ms |
40324 KB |
Output is correct |
15 |
Correct |
51 ms |
40308 KB |
Output is correct |
16 |
Correct |
54 ms |
40276 KB |
Output is correct |
17 |
Correct |
55 ms |
40328 KB |
Output is correct |
18 |
Correct |
54 ms |
40320 KB |
Output is correct |
19 |
Correct |
57 ms |
40324 KB |
Output is correct |
20 |
Correct |
55 ms |
40324 KB |
Output is correct |
21 |
Correct |
52 ms |
40200 KB |
Output is correct |
22 |
Correct |
54 ms |
40328 KB |
Output is correct |
23 |
Correct |
57 ms |
40332 KB |
Output is correct |
24 |
Correct |
54 ms |
40320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
258 ms |
41232 KB |
Output is correct |
2 |
Correct |
266 ms |
41200 KB |
Output is correct |
3 |
Correct |
324 ms |
41396 KB |
Output is correct |
4 |
Correct |
262 ms |
41140 KB |
Output is correct |
5 |
Correct |
212 ms |
42576 KB |
Output is correct |
6 |
Correct |
290 ms |
42700 KB |
Output is correct |
7 |
Correct |
205 ms |
42328 KB |
Output is correct |
8 |
Correct |
175 ms |
41432 KB |
Output is correct |
9 |
Correct |
170 ms |
41560 KB |
Output is correct |
10 |
Correct |
241 ms |
42592 KB |
Output is correct |
11 |
Correct |
234 ms |
42580 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
312 ms |
42100 KB |
Output is correct |
2 |
Correct |
293 ms |
43228 KB |
Output is correct |
3 |
Correct |
426 ms |
42288 KB |
Output is correct |
4 |
Correct |
281 ms |
42832 KB |
Output is correct |
5 |
Correct |
289 ms |
43092 KB |
Output is correct |
6 |
Correct |
282 ms |
43140 KB |
Output is correct |
7 |
Correct |
341 ms |
43216 KB |
Output is correct |
8 |
Correct |
364 ms |
43324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
375 ms |
43268 KB |
Output is correct |
2 |
Correct |
430 ms |
42320 KB |
Output is correct |
3 |
Correct |
360 ms |
41588 KB |
Output is correct |
4 |
Correct |
388 ms |
41184 KB |
Output is correct |
5 |
Correct |
273 ms |
41040 KB |
Output is correct |
6 |
Correct |
349 ms |
40948 KB |
Output is correct |
7 |
Correct |
359 ms |
42068 KB |
Output is correct |
8 |
Correct |
50 ms |
40316 KB |
Output is correct |
9 |
Correct |
56 ms |
40276 KB |
Output is correct |
10 |
Correct |
312 ms |
42592 KB |
Output is correct |
11 |
Correct |
387 ms |
43168 KB |
Output is correct |
12 |
Correct |
388 ms |
43176 KB |
Output is correct |
13 |
Correct |
393 ms |
43092 KB |
Output is correct |
14 |
Correct |
57 ms |
40296 KB |
Output is correct |
15 |
Correct |
59 ms |
40256 KB |
Output is correct |
16 |
Correct |
300 ms |
42592 KB |
Output is correct |
17 |
Correct |
455 ms |
43348 KB |
Output is correct |
18 |
Correct |
447 ms |
43340 KB |
Output is correct |
19 |
Correct |
446 ms |
43220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
52 ms |
40296 KB |
Output is correct |
2 |
Correct |
51 ms |
40300 KB |
Output is correct |
3 |
Correct |
49 ms |
40184 KB |
Output is correct |
4 |
Correct |
48 ms |
40276 KB |
Output is correct |
5 |
Correct |
50 ms |
40296 KB |
Output is correct |
6 |
Correct |
48 ms |
40256 KB |
Output is correct |
7 |
Correct |
50 ms |
40204 KB |
Output is correct |
8 |
Correct |
50 ms |
40296 KB |
Output is correct |
9 |
Correct |
51 ms |
40320 KB |
Output is correct |
10 |
Correct |
54 ms |
40180 KB |
Output is correct |
11 |
Correct |
50 ms |
40200 KB |
Output is correct |
12 |
Correct |
51 ms |
40244 KB |
Output is correct |
13 |
Correct |
62 ms |
40328 KB |
Output is correct |
14 |
Correct |
56 ms |
40324 KB |
Output is correct |
15 |
Correct |
51 ms |
40308 KB |
Output is correct |
16 |
Correct |
54 ms |
40276 KB |
Output is correct |
17 |
Correct |
55 ms |
40328 KB |
Output is correct |
18 |
Correct |
54 ms |
40320 KB |
Output is correct |
19 |
Correct |
57 ms |
40324 KB |
Output is correct |
20 |
Correct |
55 ms |
40324 KB |
Output is correct |
21 |
Correct |
52 ms |
40200 KB |
Output is correct |
22 |
Correct |
54 ms |
40328 KB |
Output is correct |
23 |
Correct |
57 ms |
40332 KB |
Output is correct |
24 |
Correct |
54 ms |
40320 KB |
Output is correct |
25 |
Correct |
258 ms |
41232 KB |
Output is correct |
26 |
Correct |
266 ms |
41200 KB |
Output is correct |
27 |
Correct |
324 ms |
41396 KB |
Output is correct |
28 |
Correct |
262 ms |
41140 KB |
Output is correct |
29 |
Correct |
212 ms |
42576 KB |
Output is correct |
30 |
Correct |
290 ms |
42700 KB |
Output is correct |
31 |
Correct |
205 ms |
42328 KB |
Output is correct |
32 |
Correct |
175 ms |
41432 KB |
Output is correct |
33 |
Correct |
170 ms |
41560 KB |
Output is correct |
34 |
Correct |
241 ms |
42592 KB |
Output is correct |
35 |
Correct |
234 ms |
42580 KB |
Output is correct |
36 |
Correct |
312 ms |
42100 KB |
Output is correct |
37 |
Correct |
293 ms |
43228 KB |
Output is correct |
38 |
Correct |
426 ms |
42288 KB |
Output is correct |
39 |
Correct |
281 ms |
42832 KB |
Output is correct |
40 |
Correct |
289 ms |
43092 KB |
Output is correct |
41 |
Correct |
282 ms |
43140 KB |
Output is correct |
42 |
Correct |
341 ms |
43216 KB |
Output is correct |
43 |
Correct |
364 ms |
43324 KB |
Output is correct |
44 |
Correct |
375 ms |
43268 KB |
Output is correct |
45 |
Correct |
430 ms |
42320 KB |
Output is correct |
46 |
Correct |
360 ms |
41588 KB |
Output is correct |
47 |
Correct |
388 ms |
41184 KB |
Output is correct |
48 |
Correct |
273 ms |
41040 KB |
Output is correct |
49 |
Correct |
349 ms |
40948 KB |
Output is correct |
50 |
Correct |
359 ms |
42068 KB |
Output is correct |
51 |
Correct |
50 ms |
40316 KB |
Output is correct |
52 |
Correct |
56 ms |
40276 KB |
Output is correct |
53 |
Correct |
312 ms |
42592 KB |
Output is correct |
54 |
Correct |
387 ms |
43168 KB |
Output is correct |
55 |
Correct |
388 ms |
43176 KB |
Output is correct |
56 |
Correct |
393 ms |
43092 KB |
Output is correct |
57 |
Correct |
57 ms |
40296 KB |
Output is correct |
58 |
Correct |
59 ms |
40256 KB |
Output is correct |
59 |
Correct |
300 ms |
42592 KB |
Output is correct |
60 |
Correct |
455 ms |
43348 KB |
Output is correct |
61 |
Correct |
447 ms |
43340 KB |
Output is correct |
62 |
Correct |
446 ms |
43220 KB |
Output is correct |
63 |
Correct |
380 ms |
41896 KB |
Output is correct |
64 |
Correct |
482 ms |
42188 KB |
Output is correct |
65 |
Correct |
394 ms |
41936 KB |
Output is correct |
66 |
Correct |
288 ms |
43248 KB |
Output is correct |
67 |
Correct |
439 ms |
43352 KB |
Output is correct |
68 |
Correct |
292 ms |
43092 KB |
Output is correct |
69 |
Correct |
284 ms |
43124 KB |
Output is correct |
70 |
Correct |
358 ms |
43280 KB |
Output is correct |
71 |
Correct |
401 ms |
43360 KB |
Output is correct |