QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#344226#8257. Marathon Race 2Alan#7 1ms3856kbC++203.4kb2024-03-03 19:37:532024-07-04 03:27:25

Judging History

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

  • [2024-07-04 03:27:25]
  • 评测
  • 测评结果：7
  • 用时：1ms
  • 内存：3856kb
查看
  • [2024-03-03 19:37:53]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct query {
	ll s, g, t;
	bool rev, ok;
} Q[500005];
int n, q;

void proc (vector<ll> x, bool rev) {
	vector<ll> ps (n+1);
	for (int i = 1; i <= n; i++) ps[i] = ps[i-1] + x[i];
	for (int i = 1; i <= q; i++) if (Q[i].rev == rev) {
		ll res;
		int right = 0;
		for (int j = 1; j <= n; j++) if (x[j] >= Q[i].g) {
			right = j;
			break;
		}
		if (!right) {
			res = n;
			if (x[1] < Q[i].s) res += (Q[i].s - x[1]) * 2;
			res += Q[i].g - Q[i].s;
			res += Q[i].g * n - ps[n];
			if (res <= Q[i].t) Q[i].ok = true;
			goto nxt;
		}
		for (int j = 1; j < right; j++) {
			res = n + Q[i].g - Q[i].s;
			if (x[1] < Q[i].s) res += (Q[i].s - x[1]) * 2;
			res += (max(x[n], Q[i].g) - x[j]) * 2;
			for (int k = 1; k < j; k++) {
				res += Q[i].g - x[k];
				res += (max(x[n], Q[i].g) - x[j]) * 2;
			}
			for (int k = j; k < right; k++) res += Q[i].g - x[k];
			for (int k = right; k <= n; k++) res += (x[k] - x[j]) + (Q[i].g - x[j]);
			if (res <= Q[i].t) {
				Q[i].ok = true;
				goto nxt;
			}
		}
		// for (int j = 1; j <= right; j++) {
		// 	ll res = n;
		// 	if (x[1] < Q[i].s) res += Q[i].s - x[1];
		// 	res += Q[i].g - Q[i].s;
		// 	res += Q[i].g*(j-1) - ps[j-1];
		// 	if (x[n] > Q[i].g) res += (Q[i].g - x[n]) * j * 2;
		// 	res += (Q[i].g - x[j]) * j;
		// 	res += ps[n] - ps[right-1] - (n-right+1) * x[j];
		// 	res += (n+1) * (Q[i].g - x[j]);
		// 	res -= (ps[right-1] - ps[j-1]) - x[j] * (right-j);
		// 	if (res <= Q[i].t) {
		// 		Q[i].ok = true;
		// 		goto nxt;
		// 	}
		// }
		// for (int j = right; j <= n; j++) {
		// 	ll res = n;
		// 	res += Q[i].g - Q[i].s;
		// 	if (x[n] > Q[i].g) res += (x[n] - Q[i].g) * 2;
		// 	res += ps[n] - ps[right-]
		// }
		res = n + Q[i].g - Q[i].s;
		if (x[1] < Q[i].s) res += (Q[i].s - x[1]) * 2;
		res += (x[n] - Q[i].g) * 2;
		for (int j = 1; j < right; j++) {
			res += Q[i].g - x[j];
			if (x[n] > Q[i].g) res += (x[n] - Q[i].g) * 2;
		}
		for (int j = right; j <= n; j++) res += x[j] - Q[i].g;
		if (res <= Q[i].t) {
			Q[i].ok = true;
			goto nxt;
		}
		res = n + Q[i].g - Q[i].s;
		res += (x[n] - Q[i].g) * 2;
		res += (Q[i].g - min(x[1], Q[i].s)) * 2;
		for (int j = 1; j < right; j++) res += Q[i].g - x[j];
		for (int j = right; j <= n; j++) {
			res += x[j] - Q[i].g;
			res += (Q[i].g - min(x[1], Q[i].s)) * 2;
		}
		if (res <= Q[i].t) {
			Q[i]. ok = true;
			goto nxt;
		}
		// ll res1 = n, res2 = n;
		// {
		// 	auto it = --lower_bound(x.begin(), x.end(), Q[i].g);
		// 	ll cnt = it - x.begin();
		// 	if (x[1] < Q[i].s) res1 += Q[i].s - x[1];
		// 	res1 += Q[i].g * cnt - ps[cnt];
		// 	if (x[n] > Q[i].g) {
		// 		res1 += (cnt+1) * (x[n] - Q[i].g) * 2;
		// 		res1 += ps[n] - ps[cnt] - Q[i].g * (n-cnt);
		// 	}
		// }
		// {
		// 	res2 += max(Q[i].g, x[n]) - Q[i].s;
		// }
		nxt: {}
	}
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int l;
	cin >> n >> l;
	vector<ll> x (n+1);
	for (int i = 1; i <= n; i++) cin >> x[i];
	sort(x.begin(), x.end());
	cin >> q;
	for (int i = 1; i <= q; i++) {
		cin >> Q[i].s >> Q[i].g >> Q[i].t;
		if (Q[i].s > Q[i].g) {
			Q[i].s = l - Q[i].s;
			Q[i].g = l - Q[i].g;
			Q[i].rev = true;
		} else Q[i].rev = false;
		Q[i].ok = false;
	}
	proc(x, 0);
	for (int i = 1; i <= n; i++) x[i] = l - x[n-i+1];
	proc(x, 1);
	for (int i = 1; i <= q; i++) cout << (Q[i].ok ? "Yes\n" : "No\n");
	return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 1ms
memory: 3560kb

input:

1 500000
166666
10
0 0 500000
0 0 499999
0 0 499998
0 0 499997
0 0 499996
0 0 5
0 0 4
0 0 3
0 0 2
0 0 1

output:

Yes
Yes
No
No
No
No
No
No
No
No

result:

ok 10 token(s): yes count is 2, no count is 8

Test #2:

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

input:

1 500000
0
10
0 0 500000
0 0 499999
0 0 499998
0 0 499997
0 0 499996
0 0 5
0 0 4
0 0 3
0 0 2
0 0 1

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 10, no count is 0

Test #3:

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

input:

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

output:

No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 6, no count is 4

Test #4:

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

input:

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

output:

No
No
No
No
No
Yes
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 5, no count is 5

Test #5:

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

input:

1 1
0
10
0 0 1
0 0 1
0 0 1
0 0 1
0 0 1
0 0 1
0 0 1
0 0 1
0 0 1
0 0 1

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 10, no count is 0

Test #6:

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

input:

7 83382
35565 7347 27797 28072 31528 45377 43857
10
0 0 160004
0 0 224969
0 0 310304
0 0 354202
0 0 310303
0 0 493150
0 0 227687
0 0 448225
0 0 88396
0 0 155211

output:

No
No
Yes
Yes
No
Yes
No
Yes
No
No

result:

ok 10 token(s): yes count is 4, no count is 6

Test #7:

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

input:

7 83382
35212 3869 11565 53219 2927 45479 40671
10
0 0 189926
0 0 419739
0 0 245553
0 0 110218
0 0 299387
0 0 1986
0 0 473275
0 0 195521
0 0 299386
0 0 246039

output:

No
Yes
No
No
Yes
No
Yes
No
No
No

result:

ok 10 token(s): yes count is 3, no count is 7

Test #8:

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

input:

7 500000
6069 96930 28374 1275 53141 1423 6225
10
0 0 388080
0 0 73883
0 0 319880
0 0 141926
0 0 144641
0 0 67306
0 0 387304
0 0 387303
0 0 236649
0 0 130438

output:

Yes
No
No
No
No
No
Yes
No
No
No

result:

ok 10 token(s): yes count is 2, no count is 8

Test #9:

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

input:

7 500000
22379 39203 896 17806 23724 7599 153
10
0 0 492328
0 0 190173
0 0 315557
0 0 190172
0 0 138962
0 0 298883
0 0 246521
0 0 194070
0 0 252592
0 0 418531

output:

Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 8, no count is 2

Test #10:

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

input:

7 500000
0 0 0 0 0 0 0
10
0 0 124229
0 0 233729
0 0 306668
0 0 499999
0 0 220256
0 0 62117
0 0 115533
0 0 48137
0 0 160004
0 0 500000

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 10, no count is 0

Test #11:

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

input:

7 498000
498000 498000 498000 498000 498000 498000 498000
10
0 0 261154
0 0 235539
0 0 224636
0 0 283789
0 0 500000
0 0 480913
0 0 326331
0 0 499999
0 0 61700
0 0 280564

output:

No
No
No
No
No
No
No
No
No
No

result:

ok 10 token(s): yes count is 0, no count is 10

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #12:

score: 7
Accepted
time: 0ms
memory: 3504kb

input:

1 2
1
8
0 0 3
0 0 4
0 2 3
0 2 4
2 0 3
2 0 4
2 2 3
2 2 4

output:

No
Yes
No
Yes
No
Yes
No
Yes

result:

ok 8 token(s): yes count is 4, no count is 4

Test #13:

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

input:

1 2
1
10
0 1 1
0 1 2
2 1 1
2 1 2
1 0 2
1 0 3
1 2 2
1 2 3
1 1 1
1 1 500000

output:

No
Yes
No
Yes
No
Yes
No
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 6, no count is 4

Test #14:

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

input:

3 11
1 5 10
10
2 6 40
2 6 41
1 6 39
1 6 40
0 6 40
0 6 41
2 7 38
2 7 39
2 5 36
2 5 37

output:

No
Yes
No
Yes
No
Yes
No
Yes
No
Yes

result:

ok 10 token(s): yes count is 5, no count is 5

Test #15:

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

input:

3 1
0 1 1
8
0 0 6
0 0 7
1 1 5
1 1 6
0 1 4
0 1 5
1 0 5
1 0 6

output:

No
Yes
No
Yes
No
Yes
No
Yes

result:

ok 8 token(s): yes count is 4, no count is 4

Test #16:

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

input:

1 499999
499999
10
0 499999 500000
0 499999 499999
0 499999 499998
0 499999 499997
0 499999 499996
0 499999 5
0 499999 4
0 499999 3
0 499999 2
0 499999 1

output:

Yes
No
No
No
No
No
No
No
No
No

result:

ok 10 token(s): yes count is 1, no count is 9

Test #17:

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

input:

1 249999
0
10
0 249999 500000
0 249999 499999
0 249999 499998
0 249999 499997
0 249999 499996
0 249999 5
0 249999 4
0 249999 3
0 249999 2
0 249999 1

output:

Yes
Yes
No
No
No
No
No
No
No
No

result:

ok 10 token(s): yes count is 2, no count is 8

Test #18:

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

input:

3 2
2 1 0
10
0 2 1
0 2 2
0 2 3
0 2 4
0 2 5
0 2 6
0 2 7
0 2 8
0 2 8
0 2 8

output:

No
No
No
No
No
No
No
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 3, no count is 7

Test #19:

score: -7
Wrong Answer
time: 0ms
memory: 3552kb

input:

7 114381
99629 67979 86546 56087 63139 108255 68436
10
93017 26947 457994
68416 90149 398467
35162 8224 500000
93764 99122 353377
43358 112463 306282
26831 9795 500000
42369 15002 500000
6450 16746 500000
7483 81534 451399
104077 82098 359317

output:

No
No
No
No
Yes
No
No
No
Yes
No

result:

wrong answer expected YES, found NO [10th token]

Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%
English 繁體中文 简体中文

Server Time: 2024-12-03 04:25:32 | OpenSource Project