QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#787262	#9646. 子集和	zhouhuanyi	100 ✓	1660ms	433092kb	C++14	3.9kb	2024-11-27 10:39:16	2024-11-27 10:39:22

Judging History

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

[2024-11-27 10:39:22]
评测

测评结果：100
用时：1660ms
内存：433092kb

查看

[2024-11-27 10:39:16]
提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#define N 10001
#define K 20
#define M 200
#define Z 1000000
#define mod 1000000007
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
void Adder(int &x,int d)
{
	x=x+d>=mod?x+d-mod:x+d;
	return;
}
void Adder2(int &x,int d)
{
	x=x+d<0?x+d+mod:x+d;
	return;
}
int MD(int x)
{
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
struct reads
{
	int num,l,r,data;
};
int n,m,q,top,ans[Z+1],a[N+1],b[N+1],dp[N+1][M+1][2],dp2[N+1][M+1][2],DP[K+1][M+1],DWP[M+1],dsp[N+1][M+1];
void solve2(int l,int r)
{
	if (l==r)
	{
		for (int i=0;i<m;++i) dsp[l][i]=DP[top][i];
		return;
	}
	int mid=(l+r)>>1;
	++top;
	for (int i=0;i<m;++i) DP[top][i]=DP[top-1][i];
	for (int i=mid+1;i<=r;++i)
	{
		for (int j=0;j<m;++j) DWP[j]=DP[top][j];
		for (int j=0;j<m;++j)
		{
			Adder(DWP[(j+a[i])%m],DP[top][j]);
			Adder(DWP[(j+b[i])%m],DP[top][j]);
		}
		for (int j=0;j<m;++j) DP[top][j]=DWP[j];
	}
	solve2(l,mid);
	for (int i=0;i<m;++i) DP[top][i]=DP[top-1][i];
	for (int i=l;i<=mid;++i)
	{
		for (int j=0;j<m;++j) DWP[j]=DP[top][j];
		for (int j=0;j<m;++j)
		{
			Adder(DWP[(j+a[i])%m],DP[top][j]);
			Adder(DWP[(j+b[i])%m],DP[top][j]);
		}
		for (int j=0;j<m;++j) DP[top][j]=DWP[j];
	}
	solve2(mid+1,r),--top;
	return;
}
void solve(int l,int r,vector<reads>p)
{
	if (l==r||p.empty()) return;
	int mid=(l+r)>>1;
	vector<reads>A;
	vector<reads>B;
	__int128 res;
	for (int i=0;i<m;++i) DP[0][i]=dp[l-1][i][0];
	solve2(l,mid);
	for (int i=0;i<m;++i) DP[0][i]=dp2[r+1][i][0];
	solve2(mid+1,r);
	for (int i=0;i<m;++i) DP[0][i]=dp[l-1][i][1];
	for (int i=l;i<=mid;++i)
	{
		for (int j=0;j<m;++j) DWP[j]=DP[0][j];
		for (int j=0;j<m;++j)
		{
			Adder(DWP[(j+a[i])%m],DP[0][j]);
			Adder(DWP[(j+b[i])%m],DP[0][j]);
		}
		for (int j=0;j<m;++j) DP[0][j]=DWP[j];
	}
	for (int i=0;i<m;++i) Adder(dsp[l][i],DP[0][i]);
	for (int i=0;i<m;++i) DP[0][i]=dp2[r+1][i][1];
	for (int i=mid+1;i<=r;++i)
	{
		for (int j=0;j<m;++j) DWP[j]=DP[0][j];
		for (int j=0;j<m;++j)
		{
			Adder(DWP[(j+a[i])%m],DP[0][j]);
			Adder(DWP[(j+b[i])%m],DP[0][j]);
		}
		for (int j=0;j<m;++j) DP[0][j]=DWP[j];
	}
	for (int i=0;i<m;++i) Adder(dsp[r][i],DP[0][i]);
	for (int i=l+1;i<=mid;++i)
		for (int j=0;j<m;++j)
			Adder(dsp[i][j],dsp[i-1][j]);
	for (int i=r-1;i>=mid+1;--i)
		for (int j=0;j<m;++j)
			Adder(dsp[i][j],dsp[i+1][j]);
	for (int i=0;i<p.size();++i)
	{
		if (p[i].l<=mid&&mid+1<=p[i].r)
		{
			res=1ll*dsp[p[i].l][0]*dsp[p[i].r][0];
			for (int j=1;j<m;++j) res+=1ll*dsp[p[i].l][j]*dsp[p[i].r][m-j];
			if (p[i].data==1) Adder(ans[p[i].num],res%mod);
			else Adder2(ans[p[i].num],-res%mod);
		}
		else if (p[i].r<=mid) A.push_back(p[i]);
		else B.push_back(p[i]);
	}
	solve(l,mid,A),solve(mid+1,r,B);
	return;
}
int main()
{
	vector<reads>p;
	int l1,r1,l2,r2;
	n=read(),m=read(),q=read(),dp[0][0][0]=1;
	for (int i=1;i<=n;++i) a[i]=read(),b[i]=read();
	for (int i=1;i<=n;++i)
		for (int j=0;j<m;++j)
		{
			for (int op=0;op<=1;++op) Adder(dp[i][j][op],dp[i-1][j][op]),Adder(dp[i][(j+a[i])%m][op],dp[i-1][j][op]),Adder(dp[i][(j+b[i])%m][op],dp[i-1][j][op]);
			Adder(dp[i][j][1],dp[i-1][j][0]);
		}
	dp2[n+1][0][0]=1;
	for (int i=n;i>=1;--i)
		for (int j=0;j<m;++j)
		{
			for (int op=0;op<=1;++op) Adder(dp2[i][j][op],dp2[i+1][j][op]),Adder(dp2[i][(j+a[i])%m][op],dp2[i+1][j][op]),Adder(dp2[i][(j+b[i])%m][op],dp2[i+1][j][op]);
			Adder(dp2[i][j][1],dp2[i+1][j][0]);
		}
	for (int i=1;i<=q;++i)
	{
		l1=read(),r1=read(),l2=read(),r2=read(),p.push_back((reads){i,r1,l2,1});
		if (l1!=1) p.push_back((reads){i,l1-1,l2,-1});
		if (r2!=n) p.push_back((reads){i,r1,r2+1,-1});
		if (l1!=1&&r2!=n) p.push_back((reads){i,l1-1,r2+1,1});
	}
	solve(1,n,p);
	for (int i=1;i<=q;++i) printf("%d\n",ans[i]);
	return 0;
}

源文件, 语言: C++14

详细

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 77ms

memory: 30112kb

input:

100 200 100000
53 120
79 20
25 123
27 67
81 138
76 2
38 78
9 110
11 176
48 181
140 66
152 17
168 11
57 37
183 83
198 99
45 20
6 178
15 133
129 12
151 109
65 98
130 121
163 110
152 191
182 158
128 171
75 103
75 135
80 103
151 112
193 97
17 99
132 25
36 131
8 34
27 15
75 22
44 99
49 68
1 71
184 48
20 ...

output:

result:

ok 100000 lines

Test #2:

score: 5

Accepted

time: 67ms

memory: 28800kb

input:

100 199 100000
128 50
63 72
51 197
196 0
59 191
151 134
102 146
119 148
50 178
68 180
21 92
115 130
135 114
98 136
78 67
178 116
135 39
123 111
34 63
107 142
143 122
167 4
34 39
196 73
161 185
126 47
197 38
19 64
143 132
67 84
62 53
91 189
128 103
130 50
46 24
102 162
129 149
173 72
126 170
36 135
1...

output:

result:

ok 100000 lines

Test #3:

score: 5

Accepted

time: 72ms

memory: 26452kb

input:

100 200 100000
143 9
38 36
64 29
186 107
8 28
5 162
55 34
179 121
199 31
54 92
22 195
81 185
50 187
1 89
51 28
49 197
194 48
79 177
106 163
139 5
48 113
102 181
143 22
183 139
31 187
41 144
183 87
199 104
146 71
5 149
95 0
62 119
49 11
60 176
176 132
165 73
116 31
104 30
160 39
115 179
176 179
76 58...

output:

result:

ok 100000 lines

Test #4:

score: 5

Accepted

time: 74ms

memory: 27076kb

input:

100 199 100000
136 28
197 197
38 6
156 149
105 94
4 19
174 80
73 170
155 38
190 20
82 156
38 45
165 161
78 164
145 110
62 125
147 81
53 123
175 184
157 113
29 159
96 108
170 93
113 114
141 46
185 36
58 153
159 73
115 126
103 175
1 67
15 25
91 36
161 198
174 104
5 75
70 195
63 79
123 20
195 42
52 60
...

output:

result:

ok 100000 lines

Subtask #2:

score: 5

Accepted

Dependency #1:

100%

Accepted

Test #5:

score: 5

Accepted

time: 81ms

memory: 31656kb

input:

500 200 100000
54 86
94 36
19 156
100 166
183 102
184 26
147 19
140 173
132 132
30 20
152 38
73 156
177 110
166 116
43 145
129 11
51 125
171 45
74 59
189 21
8 18
73 29
178 22
187 58
11 66
183 108
158 2
101 194
90 53
118 61
194 30
75 21
104 84
46 113
164 111
85 121
106 126
153 27
35 86
74 28
37 81
29...

output:

result:

ok 100000 lines

Test #6:

score: 5

Accepted

time: 92ms

memory: 29276kb

input:

500 199 100000
99 134
165 90
9 93
8 52
77 75
131 57
128 34
137 155
130 186
139 9
58 83
108 17
3 178
26 15
3 20
136 49
196 96
49 164
173 22
126 88
114 164
175 65
152 26
48 76
102 20
62 176
131 114
0 28
94 60
59 103
192 50
183 43
42 81
98 174
39 136
104 83
197 179
167 98
97 187
79 133
177 102
142 137
...

output:

result:

ok 100000 lines

Test #7:

score: 5

Accepted

time: 106ms

memory: 31176kb

input:

500 200 100000
25 181
183 146
130 171
198 161
48 14
137 199
175 195
98 163
32 149
156 53
158 52
41 127
148 48
38 199
139 179
24 135
62 10
164 31
118 136
42 142
53 154
145 113
167 46
32 161
107 128
44 63
32 20
114 139
125 112
149 41
107 191
71 120
197 175
105 168
172 2
68 96
104 128
109 6
156 155
35 ...

output:

result:

ok 100000 lines

Test #8:

score: 5

Accepted

time: 111ms

memory: 31468kb

input:

500 199 100000
125 112
10 115
49 159
55 86
198 105
73 187
89 127
108 22
100 109
9 50
90 77
21 48
13 88
18 89
127 145
195 130
197 58
143 192
108 25
1 116
100 35
171 183
123 35
104 187
90 11
56 195
41 176
50 107
157 80
141 27
6 29
60 134
117 146
26 99
29 79
5 65
181 47
38 39
9 7
63 95
152 102
65 45
18...

output:

result:

ok 100000 lines

Subtask #3:

score: 20

Accepted

Test #9:

score: 20

Accepted

time: 91ms

memory: 63336kb

input:

10000 20 100000
13 3
1 2
5 11
8 9
8 3
17 16
16 17
10 6
19 17
8 17
10 6
17 7
15 6
17 15
7 18
19 6
19 10
0 11
5 7
17 17
13 8
13 3
7 19
8 13
8 3
9 6
5 19
4 2
1 18
12 8
2 8
10 8
9 17
7 8
10 0
13 4
6 0
1 7
1 10
18 17
9 1
2 18
11 2
7 14
14 12
15 12
7 9
4 9
16 11
17 11
1 17
3 3
1 15
11 4
19 6
7 11
11 17
7 ...

output:

result:

ok 100000 lines

Test #10:

score: 20

Accepted

time: 97ms

memory: 63920kb

input:

10000 19 100000
12 1
17 0
12 1
5 11
0 2
1 3
15 10
0 0
18 15
0 6
3 11
5 7
1 5
9 15
5 14
14 15
17 5
18 14
7 17
6 12
3 14
11 2
9 9
11 11
3 1
5 3
4 5
9 1
12 7
0 13
6 8
8 12
14 6
1 18
15 9
15 18
12 1
7 16
13 5
13 12
12 14
7 16
3 0
18 8
7 0
10 3
1 16
4 5
6 10
3 13
11 9
14 5
2 16
6 7
11 13
8 7
15 3
9 17
6 ...

output:

result:

ok 100000 lines

Test #11:

score: 20

Accepted

time: 95ms

memory: 63748kb

input:

10000 20 100000
10 17
1 9
12 8
10 5
1 5
9 16
6 6
5 17
17 5
5 7
18 8
11 18
8 16
9 14
13 2
14 11
0 5
18 18
10 14
7 19
12 16
8 14
7 15
2 1
15 8
11 7
9 6
17 3
11 3
10 11
11 8
17 4
10 0
16 6
12 5
18 12
1 3
6 10
4 15
13 13
8 0
13 13
15 2
17 9
14 11
15 10
2 5
19 7
13 14
6 0
12 8
13 13
17 14
12 9
3 14
12 8
...

output:

result:

ok 100000 lines

Test #12:

score: 20

Accepted

time: 97ms

memory: 63036kb

input:

10000 19 100000
9 4
7 5
2 6
3 17
10 1
16 16
14 10
16 14
3 1
8 8
18 1
4 4
4 5
1 17
18 4
5 16
0 15
3 7
7 6
13 4
11 5
9 3
2 8
9 14
14 3
7 11
2 6
5 8
18 18
5 5
4 11
3 18
7 4
11 10
12 8
2 12
6 4
2 2
4 18
16 8
17 16
13 14
16 7
16 6
0 13
5 18
7 3
6 5
8 4
5 4
8 6
9 10
12 6
2 0
4 2
5 7
1 3
13 9
12 4
6 9
14 1...

output:

result:

ok 100000 lines

Subtask #4:

score: 15

Accepted

Dependency #3:

100%

Accepted

Test #13:

score: 15

Accepted

time: 1285ms

memory: 235780kb

input:

10000 150 1000000
113 147
44 10
15 124
135 111
34 108
141 0
130 45
48 136
33 88
125 85
35 98
74 137
48 52
103 113
0 90
49 131
128 46
92 97
132 97
51 0
9 33
120 40
49 67
132 101
116 149
95 56
46 147
134 73
9 81
117 70
40 138
65 111
82 80
99 141
109 25
2 12
36 134
135 81
107 79
30 75
87 97
101 58
116 ...

output:

result:

ok 1000000 lines

Test #14:

score: 15

Accepted

time: 1291ms

memory: 231952kb

input:

10000 149 1000000
39 86
148 63
16 105
147 89
88 3
114 1
73 75
84 50
124 54
100 76
64 8
96 76
128 79
113 136
139 112
58 71
73 75
125 37
70 47
138 135
33 4
69 76
136 96
7 54
71 0
132 104
126 92
11 9
115 135
25 145
42 144
130 9
93 144
24 20
7 70
55 10
113 40
148 7
137 91
138 121
128 139
31 77
101 125
7...

output:

result:

ok 1000000 lines

Test #15:

score: 15

Accepted

time: 1293ms

memory: 235696kb

input:

10000 150 1000000
13 121
3 73
147 60
115 86
110 62
13 59
123 104
92 23
132 98
23 17
93 106
108 99
9 51
7 124
129 24
76 56
63 88
115 122
12 36
53 69
49 64
97 129
93 73
73 30
41 118
141 63
12 142
121 118
112 130
15 147
8 22
35 127
115 145
149 132
133 3
75 29
7 33
8 49
118 48
34 26
64 73
0 104
31 87
2 ...

output:

result:

ok 1000000 lines

Test #16:

score: 15

Accepted

time: 1299ms

memory: 235900kb

input:

10000 149 1000000
37 68
2 14
125 74
2 117
78 110
93 99
91 114
133 144
27 27
104 118
111 97
23 148
134 81
75 23
57 31
27 118
76 127
41 11
140 19
35 55
99 103
49 33
82 60
17 138
37 97
51 50
143 48
50 144
8 75
123 123
40 47
110 138
75 102
146 45
93 76
138 19
121 11
94 105
83 34
145 55
26 30
19 42
88 98...

output:

result:

ok 1000000 lines

Subtask #5:

score: 15

Accepted

Dependency #3:

100%

Accepted

Test #17:

score: 15

Accepted

time: 754ms

memory: 63832kb

input:

10000 200 100000
137 37
68 58
80 53
27 98
63 129
163 78
190 39
85 119
173 140
154 146
57 176
121 137
56 28
55 157
190 93
82 59
94 20
191 134
73 104
172 78
198 164
72 97
152 159
48 129
137 193
147 111
173 142
74 124
133 19
131 149
187 27
86 199
173 6
140 55
184 101
96 37
59 93
131 31
154 136
181 31
2...

output:

result:

ok 100000 lines

Test #18:

score: 15

Accepted

time: 293ms

memory: 98512kb

input:

10000 199 100000
71 191
28 119
12 74
77 185
180 32
124 24
63 152
112 196
33 12
170 155
22 76
156 48
156 54
126 81
104 176
198 111
18 42
6 6
111 125
193 144
103 50
106 4
183 19
78 162
119 130
105 36
61 196
20 150
26 184
164 164
130 61
197 42
125 103
114 192
135 104
54 93
110 55
151 96
104 130
16 33
1...

output:

result:

ok 100000 lines

Test #19:

score: 15

Accepted

time: 370ms

memory: 80136kb

input:

10000 199 100000
163 169
71 101
136 54
192 168
112 63
151 115
143 152
111 142
145 167
192 139
98 56
175 131
119 57
185 12
4 92
138 19
94 152
88 115
28 119
43 120
162 74
180 113
132 73
25 132
185 183
124 166
38 122
91 133
123 92
41 158
56 141
49 4
140 20
44 0
59 68
116 166
1 141
122 197
102 130
116 1...

output:

result:

ok 100000 lines

Test #20:

score: 15

Accepted

time: 786ms

memory: 66088kb

input:

10000 200 100000
0 0
0 0
0 0
0 0
0 0
0 0
33 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 ...

output:

result:

ok 100000 lines

Test #21:

score: 15

Accepted

time: 388ms

memory: 81668kb

input:

10000 200 100000
126 54
113 146
92 114
136 89
88 26
1 139
103 110
28 13
135 130
159 118
112 117
1 58
38 26
97 91
132 142
86 6
198 165
146 18
33 8
51 148
67 72
169 130
141 27
16 157
22 81
91 113
140 30
78 8
136 13
176 24
9 87
193 147
15 10
160 32
53 61
55 133
96 81
160 17
76 59
175 81
85 195
172 95
4...

output:

result:

ok 100000 lines

Subtask #6:

score: 10

Accepted

Test #22:

score: 10

Accepted

time: 1641ms

memory: 239504kb

input:

10000 200 1000000
97 97
195 195
64 64
195 195
178 178
194 194
194 194
162 162
51 51
38 38
126 126
134 134
88 88
116 116
187 187
57 57
102 102
7 7
63 63
29 29
182 182
18 18
140 140
83 83
45 45
76 76
143 143
43 43
186 186
2 2
108 108
172 172
103 103
0 0
106 106
98 98
74 74
193 193
70 70
197 197
98 98
...

output:

result:

ok 1000000 lines

Test #23:

score: 10

Accepted

time: 1595ms

memory: 233240kb

input:

10000 199 1000000
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 ...

output:

result:

ok 1000000 lines

Test #24:

score: 10

Accepted

time: 1168ms

memory: 429692kb

input:

10000 199 1000000
149 149
183 183
3 3
52 52
50 50
143 143
74 74
179 179
138 138
77 77
126 126
182 182
114 114
2 2
149 149
4 4
18 18
78 78
74 74
52 52
144 144
1 1
131 131
134 134
11 11
3 3
103 103
12 12
168 168
13 13
14 14
133 133
50 50
39 39
109 109
188 188
104 104
173 173
188 188
151 151
104 104
69...

output:

result:

ok 1000000 lines

Test #25:

score: 10

Accepted

time: 1143ms

memory: 388620kb

input:

10000 200 1000000
196 196
143 143
139 139
12 12
50 50
19 19
57 57
197 197
150 150
21 21
42 42
4 4
80 80
12 12
128 128
83 83
176 176
179 179
195 195
151 151
113 113
161 161
14 14
11 11
93 93
67 67
183 183
132 132
39 39
40 40
194 194
66 66
135 135
171 171
73 73
18 18
102 102
30 30
154 154
174 174
95 9...

output:

result:

ok 1000000 lines

Subtask #7:

score: 5

Accepted

Test #26:

score: 5

Accepted

time: 1550ms

memory: 257100kb

input:

10000 200 1000000
14 75
130 107
183 182
191 153
161 32
123 1
147 44
85 129
45 12
146 172
158 191
26 48
120 30
47 0
112 146
6 197
126 62
38 42
180 120
32 141
30 122
132 41
106 56
174 21
166 78
116 11
157 40
112 88
33 59
129 146
51 143
92 136
143 36
153 154
127 34
69 131
142 143
139 33
31 137
114 19
9...

output:

result:

ok 1000000 lines

Test #27:

score: 5

Accepted

time: 1559ms

memory: 256916kb

input:

10000 199 1000000
6 185
109 92
33 23
14 61
118 9
8 148
160 159
9 146
57 143
198 12
113 181
20 85
33 79
68 172
64 67
39 69
72 37
149 187
110 33
11 185
173 59
165 127
26 33
80 109
104 59
138 159
180 5
53 98
149 28
184 147
190 101
33 166
88 143
42 61
196 130
178 58
59 88
180 146
37 120
16 118
197 4
92 ...

output:

result:

ok 1000000 lines

Test #28:

score: 5

Accepted

time: 1660ms

memory: 259772kb

input:

10000 200 1000000
74 160
138 111
52 84
154 168
15 7
48 96
39 74
195 86
30 193
23 31
11 139
77 54
61 96
150 70
123 94
111 159
187 20
138 74
149 60
128 79
34 15
130 92
61 21
86 40
22 142
195 2
196 122
145 25
124 151
150 172
123 118
57 172
23 194
77 98
162 94
44 35
196 184
3 16
185 92
16 122
131 73
23 ...

output:

result:

ok 1000000 lines

Test #29:

score: 5

Accepted

time: 1575ms

memory: 260568kb

input:

10000 199 1000000
81 66
19 9
97 30
33 127
65 63
115 54
3 19
89 41
16 8
5 48
140 106
192 17
42 17
100 33
181 160
25 114
170 179
115 78
165 5
160 60
119 156
149 69
123 127
169 90
177 35
81 37
87 23
178 101
97 59
175 160
186 138
88 61
123 134
57 134
98 38
107 22
57 25
65 102
81 23
26 53
189 97
140 83
1...

output:

result:

ok 1000000 lines

Subtask #8:

score: 25

Accepted

Dependency #2:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

100%

Accepted

Dependency #6:

100%

Accepted

Dependency #7:

100%

Accepted

Test #30:

score: 25

Accepted

time: 1582ms

memory: 232932kb

input:

10000 200 1000000
113 95
84 54
5 129
6 143
49 35
159 189
199 28
112 7
95 51
50 19
192 80
172 112
178 68
85 112
117 20
133 54
17 138
122 162
184 103
58 131
129 14
102 188
173 189
34 50
179 13
18 16
68 79
121 166
144 97
6 182
167 194
63 75
28 8
127 18
135 92
54 27
20 189
16 130
184 12
103 9
72 0
79 78...

output:

result:

ok 1000000 lines

Test #31:

score: 25

Accepted

time: 1616ms

memory: 238472kb

input:

10000 199 1000000
182 103
135 55
4 130
180 146
126 152
95 76
31 21
152 133
152 133
128 191
174 22
120 88
180 82
173 68
81 21
77 166
57 165
16 42
47 83
176 104
73 48
151 79
116 143
108 2
193 75
39 148
180 30
86 49
47 14
140 121
29 23
106 83
4 155
198 91
85 121
40 108
23 156
60 189
149 167
7 66
132 45...

output:

result:

ok 1000000 lines

Test #32:

score: 25

Accepted

time: 1620ms

memory: 233404kb

input:

10000 200 1000000
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 ...

output:

result:

ok 1000000 lines

Test #33:

score: 25

Accepted

time: 1594ms

memory: 238080kb

input:

10000 199 1000000
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 ...

output:

result:

ok 1000000 lines

Test #34:

score: 25

Accepted

time: 1167ms

memory: 433092kb

input:

10000 200 1000000
144 172
144 86
178 187
27 73
37 76
98 165
8 50
43 10
36 56
109 72
94 184
138 166
5 3
99 95
167 98
95 103
165 30
183 8
95 89
135 89
7 33
122 14
111 51
68 167
107 56
60 96
166 53
96 9
170 81
14 147
170 36
118 41
171 193
27 2
146 94
13 117
134 139
97 12
28 197
37 185
82 166
79 150
95 ...

output:

result:

ok 1000000 lines

Test #35:

score: 25

Accepted

time: 1187ms

memory: 430676kb

input:

10000 199 1000000
180 83
24 132
19 71
54 45
19 41
161 94
83 10
110 182
56 126
33 141
169 198
166 23
74 183
36 42
54 128
90 41
20 135
4 180
99 28
150 108
63 196
87 34
114 162
129 86
198 14
133 81
147 22
58 9
170 14
58 130
41 147
70 103
117 20
41 151
177 89
102 174
115 98
106 143
146 107
54 19
138 64
...

output:

result:

ok 1000000 lines

Test #36:

score: 25

Accepted

time: 1187ms

memory: 389028kb

input:

10000 200 1000000
179 159
167 197
75 37
112 71
38 87
73 8
90 64
39 156
134 39
11 149
82 82
77 118
64 95
89 54
180 5
81 72
74 60
116 150
195 130
71 197
57 18
83 166
62 121
114 8
159 112
88 183
96 151
38 84
131 196
108 193
118 49
48 165
63 80
83 180
172 88
70 83
170 64
189 65
162 85
57 139
143 77
188 ...

output:

result:

ok 1000000 lines

Test #37:

score: 25

Accepted

time: 1121ms

memory: 391544kb

input:

10000 199 1000000
167 97
198 96
26 185
78 58
162 180
152 49
155 106
14 106
5 195
116 122
2 84
93 75
148 109
160 195
189 183
180 156
102 140
99 61
0 119
131 87
15 172
7 5
147 41
157 8
134 21
98 109
196 191
164 136
1 13
197 1
177 10
145 123
163 189
107 0
86 111
64 167
79 133
76 140
172 178
48 60
157 6...

output:

result:

ok 1000000 lines