QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#99121	#3503. Misspelling	tricyzhkx	29	407ms	87688kb	C++14	1.2kb	2023-04-21 11:13:00	2023-04-21 11:13:02

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-04-21 11:13:02]
评测

测评结果：29
用时：407ms
内存：87688kb

查看

[2023-04-21 11:13:00]
提交

answer

# include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,f[500010][26],s[3][26],stk[3][500010],tp[3];
vector<pair<int,int>> vec[500010];
void upd(int &a,int b){a=(a+b)%mod;}
int main()
{
	int m,x,y,ans=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		if(x<y) vec[x].emplace_back(y,1);
		else vec[y].emplace_back(x,2);
	}
	fill(f[n],f[n]+26,1);fill(s[0],s[0]+26,1);
	stk[0][0]=stk[1][0]=stk[2][0]=n+1;
	stk[0][++tp[0]]=n;
	for(int i=n-1;i>=1;i--)
	{
		for(auto p:vec[i])
		{
			int j=p.first,k,t=p.second;
			while((k=stk[0][tp[0]])<=j)
			{
				for(int l=0;l<26;l++) upd(s[0][l],mod-f[k][l]),upd(s[t][l],f[k][l]);
				tp[0]--;stk[t][++tp[t]]=k;
			}
			while((k=stk[3-t][tp[3-t]])<=j)
			{
				for(int l=0;l<26;l++) upd(s[3-t][l],mod-f[k][l]);
				tp[3-t]--;
			}
		}
		int sum=1;
		for(int j=0;j<26;j++) upd(sum,s[0][j]);
		for(int j=0;j<26;j++) upd(f[i][j],sum),upd(f[i][j],mod-s[0][j]);
		sum=0;
		for(int j=0;j<26;j++) upd(f[i][j],sum),upd(sum,s[1][j]);
		sum=0;
		for(int j=25;j>=0;j--) upd(f[i][j],sum),upd(sum,s[2][j]);
		stk[0][++tp[0]]=i;
		for(int j=0;j<26;j++) upd(s[0][j],f[i][j]);
	}
	for(int i=0;i<26;i++) upd(ans,f[1][i]);
	cout<<ans<<endl;
	return 0;
}

源文件, 语言: C++14

详细

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 8

Accepted

time: 2ms

memory: 21676kb

input:

output:

344750796

result:

ok single line: '344750796'

Test #2:

score: -8

Wrong Answer

time: 1ms

memory: 22424kb

input:

output:

392449625

result:

wrong answer 1st lines differ - expected: '1506401', found: '392449625'

Subtask #2:

score: 0

Skipped

Dependency #1:

Subtask #3:

score: 29

Accepted

Test #19:

score: 29

Accepted

time: 339ms

memory: 87680kb

input:

500000 499999
5 6
6 7
7 11
11 15
15 18
18 20
20 21
21 22
22 23
23 27
27 28
28 29
29 30
30 32
32 33
33 35
35 36
36 37
37 43
43 44
44 46
46 47
47 48
48 49
49 51
51 52
52 53
53 54
54 58
58 61
61 63
63 64
64 65
65 66
66 69
69 70
70 76
76 77
77 78
78 80
80 81
81 83
83 87
87 88
88 90
90 92
92 93
93 96
96 ...

output:

19934265

result:

ok single line: '19934265'

Test #20:

score: 0

Accepted

time: 371ms

memory: 87688kb

input:

500000 499999
2 4
4 5
5 7
7 8
8 9
9 10
10 13
13 14
14 15
15 16
16 19
19 27
27 29
29 30
30 35
35 37
37 39
39 42
42 44
44 45
45 48
48 51
51 54
54 56
56 57
57 58
58 60
60 62
62 63
63 64
64 65
65 66
66 70
70 71
71 74
74 75
75 76
76 77
77 80
80 82
82 85
85 86
86 93
93 94
94 96
96 98
98 100
100 101
101 10...

output:

564937410

result:

ok single line: '564937410'

Test #21:

score: 0

Accepted

time: 368ms

memory: 87304kb

input:

500000 499999
1 2
2 4
4 5
5 6
6 8
8 9
9 11
11 12
12 14
14 18
18 19
19 20
20 21
21 24
24 25
25 27
27 29
29 30
30 31
31 33
33 37
37 38
38 39
39 41
41 42
42 46
46 49
49 50
50 52
52 55
55 57
57 59
59 60
60 61
61 62
62 63
63 66
66 69
69 70
70 71
71 75
75 76
76 80
80 84
84 87
87 91
91 93
93 94
94 96
96 10...

output:

502112931

result:

ok single line: '502112931'

Test #22:

score: 0

Accepted

time: 375ms

memory: 87556kb

input:

500000 499999
4 7
7 8
8 9
9 10
10 11
11 12
12 14
14 15
15 16
16 17
17 18
18 19
19 21
21 22
22 23
23 24
24 27
27 30
30 31
31 32
32 33
33 35
35 36
36 39
39 40
40 44
44 45
45 46
46 48
48 49
49 50
50 51
51 52
52 53
53 54
54 56
56 57
57 58
58 59
59 60
60 61
61 62
62 64
64 65
65 66
66 67
67 68
68 69
69 75...

output:

624913928

result:

ok single line: '624913928'

Test #23:

score: 0

Accepted

time: 366ms

memory: 87552kb

input:

500000 499999
1 3
3 4
4 5
5 6
6 8
8 9
9 10
10 12
12 14
14 15
15 19
19 21
21 25
25 28
28 29
29 30
30 31
31 32
32 33
33 34
34 36
36 37
37 42
42 45
45 46
46 48
48 49
49 50
50 54
54 56
56 57
57 58
58 61
61 67
67 68
68 70
70 71
71 73
73 74
74 75
75 76
76 78
78 79
79 80
80 82
82 84
84 85
85 87
87 93
93 96...

output:

855869095

result:

ok single line: '855869095'

Test #24:

score: 0

Accepted

time: 10ms

memory: 24840kb

input:

20000 19999
1 2
2 4
4 5
5 7
7 9
9 13
13 14
14 15
15 16
16 17
17 20
20 21
21 22
22 25
25 27
27 28
28 29
29 33
33 34
34 39
39 40
40 42
42 44
44 46
46 47
47 48
48 49
49 50
50 51
51 52
52 55
55 60
60 62
62 68
68 69
69 70
70 71
71 72
72 74
74 75
75 77
77 83
83 87
87 88
88 90
90 91
91 96
96 98
98 100
100 ...

output:

898746113

result:

ok single line: '898746113'

Test #25:

score: 0

Accepted

time: 0ms

memory: 21092kb

input:

output:

27130982

result:

ok single line: '27130982'

Test #26:

score: 0

Accepted

time: 2ms

memory: 22116kb

input:

output:

result:

ok single line: '26'

Test #27:

score: 0

Accepted

time: 407ms

memory: 82448kb

input:

500000 499999
187564 40668
40668 349455
349455 236165
236165 234125
234125 19156
19156 200503
200503 27193
27193 229119
229119 106828
106828 441617
441617 199617
199617 267010
267010 351798
351798 4127
4127 462764
462764 499225
499225 40019
40019 40149
40149 492337
492337 129118
129118 403985
403985...

output:

result:

ok single line: '26'

Subtask #4:

score: 0

Skipped

Dependency #2:

Subtask #5:

score: 0

Skipped