QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#863916#9163. Text editorfryan5 25ms4480kbC++20940b2025-01-20 02:16:112025-01-20 02:16:12

Judging History

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

  • [2025-01-20 02:16:12]
  • 评测
  • 测评结果:5
  • 用时:25ms
  • 内存:4480kb
  • [2025-01-20 02:16:11]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define int long long

const int mxn = 1e6+5;
const int inf = 1e18;

int n,l[mxn],sl,sc,el,ec;
int ans = inf;
queue<array<int,3>> bfs;

map<array<int,2>,int> memo;

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	cin>>n>>sl>>sc>>el>>ec;
	for (int i=1; i<=n; i++) {
		cin>>l[i];
	}
	bfs.push({sl,sc,0});
	while (sz(bfs)) {
		auto [x,y,d] = bfs.front(); bfs.pop();
		y = min(y,l[x]+1);
		if (memo.count({x,y}) && memo[{x,y}] <= d) continue;
		memo[{x,y}] = d;
		if (el==x) {
			ans = min(ans,d+abs(ec-y));
		}
		if (x > 1) {
			//move up
			bfs.push({x-1,y,d+1});
			//move to end of next line
			bfs.push({x-1,l[x-1]+1,d+y});
		}
		if (x < n) {
			//move down
			bfs.push({x+1,y,d+1});
			//move to beginning of line
			bfs.push({x,1,l[x]+1-y+d});
		}
	}
	cout<<ans;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 0ms
memory: 3584kb

input:

1
1 1
1 1
0

output:

0

result:

ok single line: '0'

Test #2:

score: 5
Accepted
time: 0ms
memory: 3712kb

input:

2
1 1
1 500000001
1000000000 0

output:

500000000

result:

ok single line: '500000000'

Test #3:

score: 5
Accepted
time: 0ms
memory: 3584kb

input:

2
1 429578866
1 327150572
584071526 0

output:

102428294

result:

ok single line: '102428294'

Test #4:

score: 5
Accepted
time: 0ms
memory: 3712kb

input:

2
2 1
2 1
929403468 0

output:

0

result:

ok single line: '0'

Test #5:

score: 5
Accepted
time: 0ms
memory: 3584kb

input:

2
2 1
2 1
989240738 0

output:

0

result:

ok single line: '0'

Test #6:

score: 5
Accepted
time: 0ms
memory: 3712kb

input:

2
2 1
1 371562870
436620826 0

output:

65057958

result:

ok single line: '65057958'

Test #7:

score: 5
Accepted
time: 0ms
memory: 3584kb

input:

2
1 103853165
1 705401000
836091409 0

output:

130690412

result:

ok single line: '130690412'

Test #8:

score: 5
Accepted
time: 0ms
memory: 3712kb

input:

2
2 1
2 1
924491619 0

output:

0

result:

ok single line: '0'

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 14
Accepted
time: 1ms
memory: 3968kb

input:

952
212 33
98 130
1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 13...

output:

211

result:

ok single line: '211'

Test #10:

score: 14
Accepted
time: 1ms
memory: 3968kb

input:

814
656 144
625 1537
1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642...

output:

280

result:

ok single line: '280'

Test #11:

score: 14
Accepted
time: 1ms
memory: 3968kb

input:

889
197 113
298 10
117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 1...

output:

115

result:

ok single line: '115'

Test #12:

score: 14
Accepted
time: 1ms
memory: 3968kb

input:

936
459 1445
87 1400
1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445 1445...

output:

417

result:

ok single line: '417'

Test #13:

score: 14
Accepted
time: 16ms
memory: 4224kb

input:

814
278 4540
554 2648
4656 4467 4715 4014 4136 4475 4975 4865 4132 4638 4212 4425 4190 4672 4482 4081 4602 4334 4834 4601 4971 4226 4012 4112 4122 4649 4874 4995 4860 4276 4116 4035 4770 4834 4193 4783 4083 4798 4099 4990 4258 4647 4257 4884 4408 4508 4221 4079 4604 4901 4532 4797 4987 4645 4799 474...

output:

1218

result:

ok single line: '1218'

Test #14:

score: 14
Accepted
time: 16ms
memory: 4224kb

input:

835
277 4177
547 2741
4989 4995 4552 4617 4606 4819 4734 4482 4258 4665 4854 4688 4862 4657 4212 4192 4098 4390 4187 4355 4795 4719 4509 4790 4020 4561 4873 4393 4015 4522 4740 4646 4234 4269 4233 4242 4963 4705 4433 4458 4531 4370 4432 4716 4994 4386 4034 4257 4664 4912 4360 4348 4728 4849 4283 468...

output:

1010

result:

ok single line: '1010'

Test #15:

score: 14
Accepted
time: 16ms
memory: 4352kb

input:

814
289 4614
550 2516
4098 4219 4537 4685 4782 4503 4975 4668 4459 4632 4202 4496 4300 4340 4708 4051 4271 4666 4895 4119 4903 4697 4303 4323 4739 4023 4475 4586 4980 4808 4009 4974 4169 4835 4950 4284 4367 4378 4838 4586 4170 4220 4628 4996 4111 4461 4157 4902 4031 4392 4710 4204 4797 4994 4894 494...

output:

1354

result:

ok single line: '1354'

Test #16:

score: 14
Accepted
time: 0ms
memory: 3840kb

input:

1000
1 1
999 2501
5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 50...

output:

3498

result:

ok single line: '3498'

Test #17:

score: 0
Wrong Answer
time: 25ms
memory: 4480kb

input:

1000
719 3532
294 4180
4137 4721 2657 3289 3685 4261 4940 3882 3271 3142 3749 2708 2755 2959 4092 3209 3569 3855 3761 2620 4932 3095 4464 3867 3536 4461 3785 4066 3035 3432 4161 4429 4485 4218 4889 2777 3854 4508 4619 3719 2878 3199 3555 3388 2788 4842 4511 3764 2978 4499 4581 3912 4810 3854 3308 48...

output:

722

result:

wrong answer 1st lines differ - expected: '724', found: '722'

Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #4:

score: 0
Time Limit Exceeded

Test #43:

score: 0
Time Limit Exceeded

input:

878478
323624 9772968
215921 1051399
227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227...

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%