QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#344229#8257. Marathon Race 2Alan#7 0ms3856kbC++203.5kb2024-03-03 19:38:352024-07-04 03:27:25

Judging History

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

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

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: 0ms
memory: 3568kb

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: 0ms
memory: 3596kb

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: 3820kb

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: 3556kb

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: 3616kb

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: 0ms
memory: 3656kb

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: 3856kb

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: 3620kb

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: 3820kb

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: 3852kb

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: 3800kb

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: 3556kb

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: 3660kb

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: -7
Wrong Answer
time: 0ms
memory: 3844kb

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
No
No
No
No
No
No
Yes
No
Yes

result:

wrong answer expected YES, found NO [2nd 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 22:10:17 | OpenSource Project