QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235204#6334. Passport275307894a#0 1ms4080kbC++141.5kb2023-11-02 15:57:072024-07-04 02:22:39

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 02:22:39]
  • 评测
  • 测评结果：0
  • 用时：1ms
  • 内存：4080kb
查看
  • [2023-11-02 15:57:07]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=1e2+5,M=5e5+5,K=(1<<25)+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,L[N],R[N],q,ans[N],dp[N][N];
int mx[N][20],mi[N][20];
int qx(int x,int y){int d=__lg(y-x+1);return max(mx[x][d],mx[y-(1<<d)+1][d]);}
int qi(int x,int y){int d=__lg(y-x+1);return min(mi[x][d],mi[y-(1<<d)+1][d]);}
int main(){
	int i,j,h;scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d%d",&L[i],&R[i]);
	for(i=n;i;i--){
		for(mi[i][0]=L[i],j=1;i+(1<<j)-1<=n;j++) mi[i][j]=min(mi[i][j-1],mi[i+(1<<j-1)][j-1]);
		for(mx[i][0]=R[i],j=1;i+(1<<j)-1<=n;j++) mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]);
	}
	Me(dp,0x3f);Me(ans,0x3f);
	dp[1][n]=0;
	for(i=n-1;i;i--){
		for(j=1;j<=n;j++) ans[j]=min(ans[j],dp[L[j]][R[j]]+1);
		for(j=1;j+i-1<=n;j++) {
			int l=j,r=j+i-1;
			for(h=l;h<=r;h++) dp[l][r]=min(dp[l][r],ans[h]);
			dp[l][r]=min(dp[l][r],min(dp[qi(l,r)][r],dp[l][qx(l,r)])+1);
			// cerr<<l<<' '<<r<<' '<<dp[l][r]<<'\n';
		}
	}
	int q;scanf("%d",&q);
	while(q--){
		int x;scanf("%d",&x);
		printf("%d\n",ans[x]>n+1?-1:ans[x]);
	}
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 6
Accepted
time: 1ms
memory: 4032kb

input:

2
1 1
1 2
1
1

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

2
1 2
2 2
1
1

output:

1

result:

ok single line: '1'

Test #3:

score: -6
Runtime Error

input:

196001
1 408
2 37822
1 1221
1 160899
4 62751
3 21706
2 4118
8 70696
8 4916
3 24286
9 443
8 171744
11 170980
7 3541
12 16428
8 71164
1 186827
11 234
2 23141
4 17143
21 9522
10 24
19 15936
3 15884
17 426
14 3188
17 168317
4 1560
25 35
16 39439
21 122
4 17507
8 97645
11 824
25 59856
30 9265
7 151420
37...

output:

result:

Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 16
Accepted
time: 1ms
memory: 4032kb

input:

2
1 1
1 2
1
2

output:

1

result:

ok single line: '1'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3892kb

input:

2
1 2
2 2
1
2

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0
Accepted
time: 1ms
memory: 4008kb

input:

6
1 1
2 2
1 3
3 5
5 6
1 6
1
4

output:

3

result:

ok single line: '3'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

9
1 1
2 2
3 3
1 4
2 8
5 7
4 9
8 8
9 9
1
6

output:

3

result:

ok single line: '3'

Test #12:

score: 0
Accepted
time: 0ms
memory: 4024kb

input:

9
1 1
2 2
3 3
1 4
2 8
4 9
5 7
8 8
9 9
1
7

output:

3

result:

ok single line: '3'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3956kb

input:

10
1 1
2 2
3 3
2 10
1 6
3 8
1 8
6 8
3 9
10 10
1
4

output:

2

result:

ok single line: '2'

Test #14:

score: -16
Wrong Answer
time: 1ms
memory: 4080kb

input:

285
1 13
1 16
3 16
3 25
3 94
5 100
2 92
7 10
9 10
1 270
11 11
9 93
5 43
4 115
11 15
10 66
16 20
16 58
16 22
3 124
15 31
1 59
23 23
24 24
19 28
22 126
27 27
20 89
16 218
24 42
10 135
21 156
8 187
27 265
34 35
34 41
15 233
33 107
38 44
5 284
41 42
13 169
33 51
5 81
41 89
44 52
43 50
23 86
42 62
4 95
4...

output:

5
-1
16
0
0
0
0
0
0
-1
24
0
22
0
-1
-1
-1
0
93
0
94
-1
15
-1
33
92
92
-1
-1
0
-1
-1
11
0
93
-1
15
43
43
-1
42
94
23
-1
-1
20
31
-1
-1
22
22
-1
-1
31
31
59
59
92
24
-1
-1
93
-1
-1
16
27
27
89
42
-1
-1
-1
80
0
32
-1
-1
-1
-1
66
41
-1
32
41
41
-1
-1
-1
-1
-1

result:

wrong answer 1st lines differ - expected: '4', found: '5'

Subtask #3:

score: 0
Runtime Error

Test #19:

score: 0
Runtime Error

input:

2337
1 3
2 77
1 1397
2 222
3 62
6 1896
7 10
6 950
9 9
10 16
11 455
9 588
13 16
7 1245
9 1342
8 1727
7 122
11 653
9 1094
2 57
11 81
19 1290
6 1584
16 79
14 215
21 61
27 27
16 1458
16 198
26 180
31 31
11 240
33 36
11 121
34 1542
9 1752
14 456
36 43
36 2244
40 40
4 517
42 662
31 1350
33 162
30 843
28 1...

output:

result:

Subtask #4:

score: 0
Runtime Error

Test #28:

score: 0
Runtime Error

input:

2419
1 883
1 29
3 41
4 2201
1 808
6 45
7 1456
6 134
6 1372
1 1776
4 441
7 208
5 28
4 604
7 56
9 617
8 2115
15 60
13 456
10 2071
18 23
18 39
5 39
21 35
4 75
25 44
24 640
21 30
4 860
30 31
18 78
32 779
1 927
33 34
19 59
34 181
21 502
23 155
39 39
2 254
30 641
42 50
10 2000
41 2220
18 632
35 48
27 905
...

output:

result:

Subtask #5:

score: 0
Runtime Error

Test #33:

score: 0
Runtime Error

input:

196830
1 67357
2 183304
3 23390
4 54
1 145887
3 27807
3 12376
1 1013
3 113274
3 191874
6 23342
9 2113
13 94245
3 141449
10 1727
3 51
17 99028
6 193803
8 7452
6 121537
9 23658
18 611
6 4756
4 5141
8 8547
8 66922
13 7021
9 72
3 53043
16 167381
2 15530
5 192
33 33
9 92655
10 36182
20 19992
36 24454
1 6...

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-03 19:26:05 | OpenSource Project