oj.uz

Submission #1000395

# Submission time Handle Problem Language Result Execution time Memory
1000395 2024-06-17T11:48:01 Z pcc Event Hopping (BOI22_events) C++17
100 / 100
 562 ms 43348 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 1e5+10;

int ord[mxn],perm[mxn];
pii arr[mxn];

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	int seg[mxn*4];
	void modify(int now,int l,int r,int p,int v){
		if(l == r){
			seg[now] = v;
			return;
		}
		if(mid>=p)modify(ls,l,mid,p,v);
		else modify(rs,mid+1,r,p,v);
		seg[now] = min(seg[ls],seg[rs]);
	}
	int getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now];
		if(mid>=e)return getval(ls,l,mid,s,e);
		else if(mid<s)return getval(rs,mid+1,r,s,e);
		else return min(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
	}
#undef ls
#undef rs
#undef mid
};

SEG seg;
int dp[mxn][20];
SEG dp2[20];
int N,Q;

int get_range(int rp,int lim){
	int l = 1,r = rp;
	while(l != r){
		int mid = (l+r)>>1;
		int now = ord[mid];
		if(arr[now].sc<lim)l = mid+1;
		else r = mid;
	}
	return l;
}

void calc(int b){
	for(int i = 1;i<=N;i++)seg.modify(0,1,N,i,dp[i][b-1]);
	for(int i = N;i>=1;i--){
		dp[i][b] = seg.getval(0,1,N,dp[i][b-1],i);
	}
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<=N;i++)cin>>arr[i].fs>>arr[i].sc,ord[i] = i;
	sort(ord+1,ord+N+1,[](int a,int b){return arr[a].sc == arr[b].sc?arr[a].fs<arr[b].fs:arr[a].sc<arr[b].sc;});
	for(int i = 1;i<=N;i++)perm[ord[i]] = i;
	for(int i = N;i>=1;i--){
		int now = ord[i];
		int lp = get_range(i,arr[now].fs);
		dp[i][0] = lp;
	}
	for(int i = 1;i<20;i++)calc(i);
	for(int i = 0;i<20;i++)for(int j = 1;j<=N;j++)dp2[i].modify(0,1,N,j,dp[j][i]);
	while(Q--){
		int s,t;
		cin>>s>>t;
		if(s == t){
			cout<<"0\n";
			continue;
		}
		if(arr[s].sc == arr[t].sc){
			cout<<"1\n";
			continue;
		}
		s = perm[s],t = perm[t];
		int now = t;
		if(s>t){
			cout<<"impossible\n";
			continue;
		}
		int ans = 0;
		for(int i = 19;i>=0;i--){
			if(dp2[i].getval(0,1,N,now,t)>s)now = dp2[i].getval(0,1,N,now,t),ans|=1<<i;
		}
		if(ans>N){
			cout<<"impossible\n";
		}
		else cout<<ans+1<<'\n';
	}

	/*
	for(int i = 1;i<=N;i++)cerr<<ord[i]<<' ';cout<<'\n';
	for(int i = 1;i<=N;i++){
		for(int j = 0;j<20;j++)cerr<<dp[i][j]<<' ';cout<<'\n';
	}
   */

	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37208 KB Output is correct
2 Correct 434 ms 42828 KB Output is correct
3 Correct 535 ms 42584 KB Output is correct
4 Correct 548 ms 42836 KB Output is correct
5 Correct 539 ms 42832 KB Output is correct
6 Correct 518 ms 42724 KB Output is correct
7 Correct 505 ms 42852 KB Output is correct
8 Correct 351 ms 43088 KB Output is correct
9 Correct 352 ms 43232 KB Output is correct
10 Correct 421 ms 42960 KB Output is correct
11 Correct 405 ms 43112 KB Output is correct
12 Correct 335 ms 42320 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37208 KB Output is correct
2 Correct 3 ms 37208 KB Output is correct
3 Correct 5 ms 37212 KB Output is correct
4 Correct 5 ms 37436 KB Output is correct
5 Correct 6 ms 37212 KB Output is correct
6 Correct 6 ms 37440 KB Output is correct
7 Correct 6 ms 37212 KB Output is correct
8 Correct 5 ms 37212 KB Output is correct
9 Correct 5 ms 37344 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37208 KB Output is correct
2 Correct 3 ms 37208 KB Output is correct
3 Correct 5 ms 37212 KB Output is correct
4 Correct 5 ms 37436 KB Output is correct
5 Correct 6 ms 37212 KB Output is correct
6 Correct 6 ms 37440 KB Output is correct
7 Correct 6 ms 37212 KB Output is correct
8 Correct 5 ms 37212 KB Output is correct
9 Correct 5 ms 37344 KB Output is correct
10 Correct 3 ms 37208 KB Output is correct
11 Correct 3 ms 37356 KB Output is correct
12 Correct 5 ms 37212 KB Output is correct
13 Correct 5 ms 37212 KB Output is correct
14 Correct 5 ms 37212 KB Output is correct
15 Correct 6 ms 37212 KB Output is correct
16 Correct 5 ms 37212 KB Output is correct
17 Correct 5 ms 37380 KB Output is correct
18 Correct 6 ms 33116 KB Output is correct
19 Correct 120 ms 35000 KB Output is correct
20 Correct 135 ms 32912 KB Output is correct
21 Correct 88 ms 33252 KB Output is correct
22 Correct 50 ms 33364 KB Output is correct
23 Correct 46 ms 33192 KB Output is correct
24 Correct 47 ms 35156 KB Output is correct
25 Correct 97 ms 32852 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37208 KB Output is correct
2 Correct 3 ms 37208 KB Output is correct
3 Correct 5 ms 37212 KB Output is correct
4 Correct 5 ms 37436 KB Output is correct
5 Correct 6 ms 37212 KB Output is correct
6 Correct 6 ms 37440 KB Output is correct
7 Correct 6 ms 37212 KB Output is correct
8 Correct 5 ms 37212 KB Output is correct
9 Correct 5 ms 37344 KB Output is correct
10 Correct 3 ms 37208 KB Output is correct
11 Correct 4 ms 37212 KB Output is correct
12 Correct 5 ms 37212 KB Output is correct
13 Correct 5 ms 37212 KB Output is correct
14 Correct 5 ms 37400 KB Output is correct
15 Correct 6 ms 37212 KB Output is correct
16 Correct 5 ms 37376 KB Output is correct
17 Correct 5 ms 37212 KB Output is correct
18 Correct 5 ms 37208 KB Output is correct
19 Correct 336 ms 40860 KB Output is correct
20 Correct 332 ms 40020 KB Output is correct
21 Correct 313 ms 40788 KB Output is correct
22 Correct 350 ms 40892 KB Output is correct
23 Correct 307 ms 41044 KB Output is correct
24 Correct 349 ms 41044 KB Output is correct
25 Correct 304 ms 40276 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 42820 KB Output is correct
2 Correct 562 ms 42596 KB Output is correct
3 Correct 536 ms 42604 KB Output is correct
4 Correct 382 ms 43092 KB Output is correct
5 Correct 424 ms 43092 KB Output is correct
6 Correct 444 ms 42836 KB Output is correct
7 Correct 437 ms 42836 KB Output is correct
8 Correct 470 ms 42832 KB Output is correct
9 Correct 314 ms 40836 KB Output is correct
10 Correct 441 ms 42576 KB Output is correct
11 Correct 373 ms 42388 KB Output is correct
12 Correct 462 ms 42500 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37208 KB Output is correct
2 Correct 434 ms 42828 KB Output is correct
3 Correct 535 ms 42584 KB Output is correct
4 Correct 548 ms 42836 KB Output is correct
5 Correct 539 ms 42832 KB Output is correct
6 Correct 518 ms 42724 KB Output is correct
7 Correct 505 ms 42852 KB Output is correct
8 Correct 351 ms 43088 KB Output is correct
9 Correct 352 ms 43232 KB Output is correct
10 Correct 421 ms 42960 KB Output is correct
11 Correct 405 ms 43112 KB Output is correct
12 Correct 335 ms 42320 KB Output is correct
13 Correct 4 ms 37208 KB Output is correct
14 Correct 3 ms 37208 KB Output is correct
15 Correct 5 ms 37212 KB Output is correct
16 Correct 5 ms 37436 KB Output is correct
17 Correct 6 ms 37212 KB Output is correct
18 Correct 6 ms 37440 KB Output is correct
19 Correct 6 ms 37212 KB Output is correct
20 Correct 5 ms 37212 KB Output is correct
21 Correct 5 ms 37344 KB Output is correct
22 Correct 3 ms 37208 KB Output is correct
23 Correct 3 ms 37356 KB Output is correct
24 Correct 5 ms 37212 KB Output is correct
25 Correct 5 ms 37212 KB Output is correct
26 Correct 5 ms 37212 KB Output is correct
27 Correct 6 ms 37212 KB Output is correct
28 Correct 5 ms 37212 KB Output is correct
29 Correct 5 ms 37380 KB Output is correct
30 Correct 6 ms 33116 KB Output is correct
31 Correct 120 ms 35000 KB Output is correct
32 Correct 135 ms 32912 KB Output is correct
33 Correct 88 ms 33252 KB Output is correct
34 Correct 50 ms 33364 KB Output is correct
35 Correct 46 ms 33192 KB Output is correct
36 Correct 47 ms 35156 KB Output is correct
37 Correct 97 ms 32852 KB Output is correct
38 Correct 3 ms 37208 KB Output is correct
39 Correct 4 ms 37212 KB Output is correct
40 Correct 5 ms 37212 KB Output is correct
41 Correct 5 ms 37212 KB Output is correct
42 Correct 5 ms 37400 KB Output is correct
43 Correct 6 ms 37212 KB Output is correct
44 Correct 5 ms 37376 KB Output is correct
45 Correct 5 ms 37212 KB Output is correct
46 Correct 5 ms 37208 KB Output is correct
47 Correct 336 ms 40860 KB Output is correct
48 Correct 332 ms 40020 KB Output is correct
49 Correct 313 ms 40788 KB Output is correct
50 Correct 350 ms 40892 KB Output is correct
51 Correct 307 ms 41044 KB Output is correct
52 Correct 349 ms 41044 KB Output is correct
53 Correct 304 ms 40276 KB Output is correct
54 Correct 436 ms 42820 KB Output is correct
55 Correct 562 ms 42596 KB Output is correct
56 Correct 536 ms 42604 KB Output is correct
57 Correct 382 ms 43092 KB Output is correct
58 Correct 424 ms 43092 KB Output is correct
59 Correct 444 ms 42836 KB Output is correct
60 Correct 437 ms 42836 KB Output is correct
61 Correct 470 ms 42832 KB Output is correct
62 Correct 314 ms 40836 KB Output is correct
63 Correct 441 ms 42576 KB Output is correct
64 Correct 373 ms 42388 KB Output is correct
65 Correct 462 ms 42500 KB Output is correct
66 Correct 3 ms 37212 KB Output is correct
67 Correct 430 ms 42724 KB Output is correct
68 Correct 551 ms 42604 KB Output is correct
69 Correct 551 ms 42804 KB Output is correct
70 Correct 523 ms 42836 KB Output is correct
71 Correct 527 ms 42836 KB Output is correct
72 Correct 507 ms 42708 KB Output is correct
73 Correct 352 ms 43200 KB Output is correct
74 Correct 351 ms 43348 KB Output is correct
75 Correct 447 ms 43092 KB Output is correct
76 Correct 421 ms 43120 KB Output is correct
77 Correct 335 ms 42352 KB Output is correct
78 Correct 4 ms 37212 KB Output is correct
79 Correct 5 ms 31324 KB Output is correct
80 Correct 5 ms 33332 KB Output is correct
81 Correct 5 ms 31324 KB Output is correct
82 Correct 4 ms 31324 KB Output is correct
83 Correct 5 ms 31324 KB Output is correct
84 Correct 5 ms 37428 KB Output is correct
85 Correct 5 ms 37212 KB Output is correct
86 Correct 122 ms 36952 KB Output is correct
87 Correct 142 ms 37140 KB Output is correct
88 Correct 87 ms 37204 KB Output is correct
89 Correct 49 ms 33364 KB Output is correct
90 Correct 46 ms 33108 KB Output is correct
91 Correct 48 ms 37184 KB Output is correct
92 Correct 90 ms 32852 KB Output is correct
93 Correct 335 ms 40864 KB Output is correct
94 Correct 346 ms 40064 KB Output is correct
95 Correct 321 ms 40788 KB Output is correct
96 Correct 338 ms 40860 KB Output is correct
97 Correct 305 ms 40844 KB Output is correct
98 Correct 339 ms 41044 KB Output is correct
99 Correct 297 ms 40188 KB Output is correct
100 Correct 440 ms 42836 KB Output is correct
101 Correct 433 ms 42816 KB Output is correct
102 Correct 459 ms 42864 KB Output is correct
103 Correct 471 ms 42496 KB Output is correct
104 Correct 385 ms 42324 KB Output is correct
105 Correct 472 ms 42580 KB Output is correct
106 Correct 418 ms 42216 KB Output is correct
107 Correct 492 ms 42068 KB Output is correct
108 Correct 425 ms 42724 KB Output is correct
109 Correct 372 ms 42860 KB Output is correct
110 Correct 379 ms 42652 KB Output is correct
111 Correct 371 ms 42836 KB Output is correct