# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
824495 | 2023-08-14T06:56:31 Z | Amylopectin | Railway Trip 2 (JOI22_ho_t4) | C++14 | 2000 ms | 4404 KB |
#include <stdio.h> #include <iostream> #include <algorithm> using namespace std; const int mxn = 1e6 + 10; int le[mxn] = {},ri[mxn] = {},rel,rer,ldo[mxn] = {},rdo[mxn] = {}; int bui(int cl,int cr,int no) { if(cl == cr) { // le[no] = cl; // ri[no] = cl; le[no] = -1; ri[no] = -1; return 0; } int mid = (cl+cr) / 2; bui(cl,mid,no*2); bui(mid+1,cr,no*2+1); le[no] = -1; ri[no] = -1; // le[no] = min(le[no*2],le[no*2+1]); // ri[no] = max(ri[no*2],ri[no*2+1]); return 0; } int ad(int cl,int cr,int no,int tl,int tr,int ava) { if(cl > tr || cr < tl) { return 0; } if(cl >= tl && cr <= tr) { if(le[no] == -1) { le[no] = ava; } else { le[no] = min(le[no],ava); } if(ri[no] == -1) { ri[no] = ava; } else { ri[no] = max(ri[no],ava); } return 0; } int mid = (cl+cr) / 2; ad(cl,mid,no*2,tl,tr,ava); ad(mid+1,cr,no*2+1,tl,tr,ava); // le[no] = min(le[no*2],le[no*2+1]); // ri[no] = max(ri[no*2],ri[no*2+1]); return 0; } int bui2(int cl,int cr,int no,int ldow,int rdow) { if(le[no] != -1) { if(ldow != -1) { ldow = min(ldow,le[no]); } else { ldow = le[no]; } } if(ri[no] != -1) { if(rdow != -1) { rdow = max(rdow,ri[no]); } else { rdow = ri[no]; } } if(cl == cr) { le[no] = ldow; ri[no] = rdow; return 0; } int mid = (cl+cr) / 2; bui2(cl,mid,no*2,ldow,rdow); bui2(mid+1,cr,no*2+1,ldow,rdow); if(le[no*2] == -1) { le[no] = le[no*2 +1]; } else if(le[no*2+1] == -1) { le[no] = le[no*2]; } else { le[no] = min(le[no*2],le[no*2+1]); } if(ri[no*2] == -1) { ri[no] = ri[no*2 +1]; } else if(ri[no*2+1] == -1) { ri[no] = ri[no*2]; } else { ri[no] = max(ri[no*2],ri[no*2+1]); } return 0; } int fii(int cl,int cr,int no,int tl,int tr) { if(cl > tr || cr < tl) { return 0; } if(cl >= tl && cr <= tr) { if(le[no] != -1) rel = min(le[no],rel); if(ri[no] != -1) rer = max(ri[no],rer); return 0; } int mid = (cl+cr) / 2; fii(cl,mid,no*2,tl,tr); fii(mid+1,cr,no*2+1,tl,tr); return 0; } int main() { int i,j,k,n,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of; scanf("%d %d %d",&n,&ex,&m); bui(1,n,1); for(i=0; i<m; i++) { scanf("%d %d",&cn,&cm); if(cn < cm) { ad(1,n,1,cn,min(cn+ex-1,cm),cm); } else { ad(1,n,1,max(cn-ex+1,cm),cn,cm); } } bui2(1,n,1,-1,-1); scanf("%d",&q); for(i=0; i<q; i++) { scanf("%d %d",&cn,&cm); cl = cn; cr = cn; of = 0; cou = 0; while(1) { rel = cl; rer = cr; fii(1,n,1,cl,cr); cou ++; if(rel <= cm && cm <= rer) { of = 1; break; } if(rel == cl && rer == cr) { of = 0; break; } cl = rel; cr = rer; } if(of == 0) { printf("-1\n"); } else { printf("%d\n",cou); } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 340 KB | Output is correct |
2 | Correct | 2 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 308 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 304 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 1 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 1 ms | 212 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 340 KB | Output is correct |
2 | Correct | 2 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 308 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 304 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 1 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 1 ms | 212 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 162 ms | 340 KB | Output is correct |
14 | Correct | 91 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 2 ms | 340 KB | Output is correct |
17 | Correct | 35 ms | 340 KB | Output is correct |
18 | Correct | 1 ms | 340 KB | Output is correct |
19 | Correct | 2 ms | 340 KB | Output is correct |
20 | Correct | 2 ms | 384 KB | Output is correct |
21 | Correct | 1 ms | 340 KB | Output is correct |
22 | Correct | 2 ms | 340 KB | Output is correct |
23 | Correct | 4 ms | 340 KB | Output is correct |
24 | Correct | 4 ms | 392 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 31 ms | 2516 KB | Output is correct |
2 | Correct | 30 ms | 2516 KB | Output is correct |
3 | Correct | 39 ms | 2628 KB | Output is correct |
4 | Correct | 25 ms | 2624 KB | Output is correct |
5 | Correct | 91 ms | 3364 KB | Output is correct |
6 | Correct | 62 ms | 4404 KB | Output is correct |
7 | Correct | 65 ms | 4388 KB | Output is correct |
8 | Correct | 50 ms | 3492 KB | Output is correct |
9 | Correct | 48 ms | 3496 KB | Output is correct |
10 | Correct | 69 ms | 4392 KB | Output is correct |
11 | Correct | 69 ms | 4404 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2064 ms | 2616 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 123 ms | 4152 KB | Output is correct |
2 | Execution timed out | 2079 ms | 3752 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 340 KB | Output is correct |
2 | Correct | 2 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 308 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 304 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 1 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 1 ms | 212 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 162 ms | 340 KB | Output is correct |
14 | Correct | 91 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 2 ms | 340 KB | Output is correct |
17 | Correct | 35 ms | 340 KB | Output is correct |
18 | Correct | 1 ms | 340 KB | Output is correct |
19 | Correct | 2 ms | 340 KB | Output is correct |
20 | Correct | 2 ms | 384 KB | Output is correct |
21 | Correct | 1 ms | 340 KB | Output is correct |
22 | Correct | 2 ms | 340 KB | Output is correct |
23 | Correct | 4 ms | 340 KB | Output is correct |
24 | Correct | 4 ms | 392 KB | Output is correct |
25 | Correct | 31 ms | 2516 KB | Output is correct |
26 | Correct | 30 ms | 2516 KB | Output is correct |
27 | Correct | 39 ms | 2628 KB | Output is correct |
28 | Correct | 25 ms | 2624 KB | Output is correct |
29 | Correct | 91 ms | 3364 KB | Output is correct |
30 | Correct | 62 ms | 4404 KB | Output is correct |
31 | Correct | 65 ms | 4388 KB | Output is correct |
32 | Correct | 50 ms | 3492 KB | Output is correct |
33 | Correct | 48 ms | 3496 KB | Output is correct |
34 | Correct | 69 ms | 4392 KB | Output is correct |
35 | Correct | 69 ms | 4404 KB | Output is correct |
36 | Execution timed out | 2064 ms | 2616 KB | Time limit exceeded |
37 | Halted | 0 ms | 0 KB | - |