Submission #579994

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
579994	2022-06-20T12:37:18 Z	haojiandan	Event Hopping (BOI22_events)	C++14	100 / 100	234 ms	19276 KB

events

// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
    t=0; char ch=getchar(); int f=1;
    while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
    if (t<0) { putchar('-'); write(-t); return; }
    if (t>9) write(t/10);
    putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
const int maxn=(2e5)+10;
int n,q,tot;
struct node {
    int x,y,z,id;
} Q[maxn],d[maxn];
bool cmp(node A,node B) { return A.x<B.x; }
int ans[maxn];
int lsh[maxn],bad[maxn];
int tr[maxn*4],lazy[maxn*4];
int MN(int a,int b) { if (a==n+1) return b; if (b==n+1) return a; if (d[a].x<d[b].x) return a; return b; }
void puttag(int root,int delta) {
    lazy[root]=MN(lazy[root],delta);
    tr[root]=MN(tr[root],delta);
}
void pushdown(int root) {
    puttag(root<<1,lazy[root]),puttag(root<<1|1,lazy[root]),lazy[root]=n+1;
}
void add(int x,int l,int r,int root,int delta) {
    if (l==r) { puttag(root,delta); return; }
    int mid=(l+r)>>1; pushdown(root);
    if (x<=mid) add(x,l,mid,root<<1,delta);
    else add(x,mid+1,r,root<<1|1,delta);
    tr[root]=MN(tr[root<<1],tr[root<<1|1]);
}
int rem[maxn],f[maxn][20],N;
int query(int L,int R,int l,int r,int root) {
    if (L<=l&&r<=R) return tr[root];
    int mid=(l+r)>>1,res=n+1; pushdown(root);
    if (L<=mid) res=MN(res,query(L,R,l,mid,root<<1));
    if (mid<R) res=MN(res,query(L,R,mid+1,r,root<<1|1));
    return res;
}
int main() {
    //freopen("1.txt","r",stdin);
    read(n),read(q);
    for (int i=1;i<=n;i++) read(d[i].x),read(d[i].y),lsh[++N]=d[i].x,lsh[++N]=d[i].y;
    sort(lsh+1,lsh+N+1),N=unique(lsh+1,lsh+N+1)-lsh-1;
    for (int i=1;i<=N*4;i++) tr[i]=lazy[i]=n+1;
    for (int i=1;i<=n;i++) {
        int r=lower_bound(lsh+1,lsh+N+1,d[i].y)-lsh;
        add(r,1,N,1,i);
    }
    for (int i=1;i<=n;i++) {
        int l=lower_bound(lsh+1,lsh+N+1,d[i].x)-lsh;
        int r=lower_bound(lsh+1,lsh+N+1,d[i].y)-lsh;
        f[i][0]=query(l,r,1,N,1);
    //    printf("i=%d,f=%d\n",i,f[i][0]);
    }
    for (int i=1;i<=19;i++)
    for (int j=1;j<=n;j++)
        f[j][i]=f[f[j][i-1]][i-1];
    for (int i=1;i<=q;i++) {
        int x,y;
        read(x),read(y);
        if (x==y) { puts("0"); continue; }
        if (d[x].y>=d[y].x&&d[x].y<=d[y].y) { puts("1"); continue; }
        for (int j=19;j>=0;j--)
            if (d[f[y][j]].x>d[x].y) y=f[y][j],ans[i]+=1<<j;
        if (d[y].x>d[x].y) y=f[y][0],ans[i]++;
        //printf(" %d\n",y);
        if (d[x].y>=d[y].x&&d[x].y<=d[y].y) printf("%d\n",ans[i]+(x!=y));
        else puts("impossible");
    }
    return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
 
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
   
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
   
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	153 ms	14548 KB	Output is correct
3	Correct	162 ms	14564 KB	Output is correct
4	Correct	185 ms	14508 KB	Output is correct
5	Correct	174 ms	14864 KB	Output is correct
6	Correct	166 ms	15224 KB	Output is correct
7	Correct	175 ms	15332 KB	Output is correct
8	Correct	166 ms	18128 KB	Output is correct
9	Correct	200 ms	18252 KB	Output is correct
10	Correct	181 ms	14880 KB	Output is correct
11	Correct	177 ms	16372 KB	Output is correct
12	Correct	96 ms	15068 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	2 ms	468 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	480 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	2 ms	468 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	480 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	2 ms	468 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	2 ms	468 KB	Output is correct
17	Correct	2 ms	468 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	28 ms	1888 KB	Output is correct
20	Correct	37 ms	1888 KB	Output is correct
21	Correct	38 ms	2124 KB	Output is correct
22	Correct	21 ms	2112 KB	Output is correct
23	Correct	18 ms	2168 KB	Output is correct
24	Correct	17 ms	1848 KB	Output is correct
25	Correct	24 ms	1792 KB	Output is correct

Subtask #4

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	2 ms	468 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	480 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	2 ms	476 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	2 ms	472 KB	Output is correct
16	Correct	2 ms	468 KB	Output is correct
17	Correct	2 ms	468 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	166 ms	15052 KB	Output is correct
20	Correct	142 ms	13792 KB	Output is correct
21	Correct	148 ms	13696 KB	Output is correct
22	Correct	143 ms	14796 KB	Output is correct
23	Correct	187 ms	16976 KB	Output is correct
24	Correct	175 ms	16640 KB	Output is correct
25	Correct	25 ms	10508 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	161 ms	14512 KB	Output is correct
2	Correct	172 ms	14540 KB	Output is correct
3	Correct	200 ms	14496 KB	Output is correct
4	Correct	170 ms	18208 KB	Output is correct
5	Correct	195 ms	14884 KB	Output is correct
6	Correct	210 ms	17996 KB	Output is correct
7	Correct	234 ms	17868 KB	Output is correct
8	Correct	224 ms	18088 KB	Output is correct
9	Correct	190 ms	16860 KB	Output is correct
10	Correct	218 ms	17508 KB	Output is correct
11	Correct	205 ms	17240 KB	Output is correct
12	Correct	215 ms	17476 KB	Output is correct

Subtask #6

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	153 ms	14548 KB	Output is correct
3	Correct	162 ms	14564 KB	Output is correct
4	Correct	185 ms	14508 KB	Output is correct
5	Correct	174 ms	14864 KB	Output is correct
6	Correct	166 ms	15224 KB	Output is correct
7	Correct	175 ms	15332 KB	Output is correct
8	Correct	166 ms	18128 KB	Output is correct
9	Correct	200 ms	18252 KB	Output is correct
10	Correct	181 ms	14880 KB	Output is correct
11	Correct	177 ms	16372 KB	Output is correct
12	Correct	96 ms	15068 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	2 ms	468 KB	Output is correct
16	Correct	2 ms	468 KB	Output is correct
17	Correct	1 ms	468 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct
19	Correct	1 ms	480 KB	Output is correct
20	Correct	1 ms	468 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	2 ms	468 KB	Output is correct
25	Correct	1 ms	468 KB	Output is correct
26	Correct	1 ms	468 KB	Output is correct
27	Correct	1 ms	468 KB	Output is correct
28	Correct	2 ms	468 KB	Output is correct
29	Correct	2 ms	468 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	28 ms	1888 KB	Output is correct
32	Correct	37 ms	1888 KB	Output is correct
33	Correct	38 ms	2124 KB	Output is correct
34	Correct	21 ms	2112 KB	Output is correct
35	Correct	18 ms	2168 KB	Output is correct
36	Correct	17 ms	1848 KB	Output is correct
37	Correct	24 ms	1792 KB	Output is correct
38	Correct	0 ms	340 KB	Output is correct
39	Correct	0 ms	340 KB	Output is correct
40	Correct	1 ms	468 KB	Output is correct
41	Correct	2 ms	476 KB	Output is correct
42	Correct	1 ms	468 KB	Output is correct
43	Correct	2 ms	472 KB	Output is correct
44	Correct	2 ms	468 KB	Output is correct
45	Correct	2 ms	468 KB	Output is correct
46	Correct	0 ms	340 KB	Output is correct
47	Correct	166 ms	15052 KB	Output is correct
48	Correct	142 ms	13792 KB	Output is correct
49	Correct	148 ms	13696 KB	Output is correct
50	Correct	143 ms	14796 KB	Output is correct
51	Correct	187 ms	16976 KB	Output is correct
52	Correct	175 ms	16640 KB	Output is correct
53	Correct	25 ms	10508 KB	Output is correct
54	Correct	161 ms	14512 KB	Output is correct
55	Correct	172 ms	14540 KB	Output is correct
56	Correct	200 ms	14496 KB	Output is correct
57	Correct	170 ms	18208 KB	Output is correct
58	Correct	195 ms	14884 KB	Output is correct
59	Correct	210 ms	17996 KB	Output is correct
60	Correct	234 ms	17868 KB	Output is correct
61	Correct	224 ms	18088 KB	Output is correct
62	Correct	190 ms	16860 KB	Output is correct
63	Correct	218 ms	17508 KB	Output is correct
64	Correct	205 ms	17240 KB	Output is correct
65	Correct	215 ms	17476 KB	Output is correct
66	Correct	0 ms	340 KB	Output is correct
67	Correct	156 ms	14540 KB	Output is correct
68	Correct	179 ms	14620 KB	Output is correct
69	Correct	191 ms	14508 KB	Output is correct
70	Correct	180 ms	14932 KB	Output is correct
71	Correct	170 ms	15220 KB	Output is correct
72	Correct	167 ms	15308 KB	Output is correct
73	Correct	175 ms	18248 KB	Output is correct
74	Correct	180 ms	18260 KB	Output is correct
75	Correct	171 ms	15164 KB	Output is correct
76	Correct	184 ms	16400 KB	Output is correct
77	Correct	99 ms	15008 KB	Output is correct
78	Correct	0 ms	340 KB	Output is correct
79	Correct	1 ms	468 KB	Output is correct
80	Correct	1 ms	468 KB	Output is correct
81	Correct	1 ms	468 KB	Output is correct
82	Correct	1 ms	468 KB	Output is correct
83	Correct	1 ms	468 KB	Output is correct
84	Correct	3 ms	468 KB	Output is correct
85	Correct	1 ms	340 KB	Output is correct
86	Correct	32 ms	2004 KB	Output is correct
87	Correct	26 ms	1884 KB	Output is correct
88	Correct	29 ms	2144 KB	Output is correct
89	Correct	21 ms	2192 KB	Output is correct
90	Correct	18 ms	2116 KB	Output is correct
91	Correct	16 ms	1792 KB	Output is correct
92	Correct	22 ms	1840 KB	Output is correct
93	Correct	137 ms	13600 KB	Output is correct
94	Correct	161 ms	13632 KB	Output is correct
95	Correct	151 ms	13632 KB	Output is correct
96	Correct	139 ms	14764 KB	Output is correct
97	Correct	180 ms	16796 KB	Output is correct
98	Correct	181 ms	16740 KB	Output is correct
99	Correct	25 ms	10452 KB	Output is correct
100	Correct	210 ms	17812 KB	Output is correct
101	Correct	211 ms	18272 KB	Output is correct
102	Correct	206 ms	19148 KB	Output is correct
103	Correct	209 ms	19060 KB	Output is correct
104	Correct	213 ms	18380 KB	Output is correct
105	Correct	221 ms	19276 KB	Output is correct
106	Correct	166 ms	15772 KB	Output is correct
107	Correct	192 ms	16828 KB	Output is correct
108	Correct	186 ms	16472 KB	Output is correct
109	Correct	165 ms	15428 KB	Output is correct
110	Correct	204 ms	18252 KB	Output is correct
111	Correct	198 ms	17740 KB	Output is correct