QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#864010#9163. Text editorfryan5 1ms8040kbC++202.8kb2025-01-20 07:17:482025-01-20 07:17:49

Judging History

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

  • [2025-01-20 07:17:49]
  • 评测
  • 测评结果:5
  • 用时:1ms
  • 内存:8040kb
  • [2025-01-20 07:17:48]
  • 提交

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

namespace static_rmq {
	//see yosupo for usage details
	const int K = 19;
	const int mxn = 5e5+5;
	int N;
	int st[K+1][mxn];
	void build() {
		for (int i=1; i<=K; i++)
		    for (int j=0; j+(1<<i)<=N; j++)
		        st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
	}
	void init(int* arr, int size) {
		copy(arr,arr+size,st[0]);
		N = size;
		build();
	}
	int query(int l, int r) {
		int i=log2(r-l+1);
		return min(st[i][l],st[i][r-(1<<i)+1]);
	}
};

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

int n,l[mxn],sl,sc,el,ec;
int ans = inf;

priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> dij;
map<array<int,2>,int> memo;

int r_search(int l, int r, int v, int p) {
	if (l==r) return r;
	if (l+1==r) {
		if (static_rmq::query(r,p-1) < v) return r;
		return l;
	}
	int m = (l+r)/2;
	if (static_rmq::query(m,p-1) < v) {
		return r_search(m,r,v,p);
	}
	return r_search(l,r,v,p);
}
int l_search(int l, int r, int v, int p) {
	if (l==r) return r;
	if (l+1==r) {
		if (static_rmq::query(p+1,l) < v) return l;
		return r;
	}
	int m = (l+r)/2;
	if (static_rmq::query(p+1,m) < v) {
		return l_search(l,m,v,p);
	}
	return l_search(m,r,v,p);
}

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];
	}
	l[0] = l[n+1] = -1;
	static_rmq::init(l,n+1);
	
	dij.push({0,sl,sc});
	
	while (sz(dij)) {
		auto [d,x,y] = dij.top(); dij.pop();
		if (d >= ans) break;
		if (memo.count({x,y}) && memo[{x,y}] <= d) continue;
//		cout<<x<<" "<<y<<"  "<<d<<"\n";
		memo[{x,y}] = d;
		if (x == el) {
			ans = min(ans,d+abs(y-ec));
		}
		//case 1 - go to bottom of current
		dij.push({d+y-1,x,1});
		//case 2 - go to top of current
		dij.push({d+l[x]+1-y,x,l[x]+1});
		//case 3 - go to first of next by going up
		if (x<n) {
			dij.push({d+l[x]+2-y,x+1,1});
		}
		//case 4 - go to last of before by going down
		if (x>1) {
			dij.push({d+y,x-1,l[x-1]+1});
		}
		//case 5 - go to next if at bottom
		if (y==1) {
			if (x>1) dij.push({d+1,x-1,1});
			if (x<n) dij.push({d+1,x+1,1});
		}
		//case 6 - go to next lowest if not at bottom
		if (y > 1) {
			int f = r_search(0,x-1,y,x);
//			cout<<f<<endl;
			if (f != 0) {
				dij.push({d+x-f,f,l[f]+1});
			}
			f = l_search(x+1,n+1,y,x);
			if (f != n+1) {
				dij.push({d+f-x,f,l[f]+1});
			}
		}
		//case 7 - go directly to end
		if (x > el) {
			int ny = min(y,static_rmq::query(el,x)+1);
			dij.push({d+x-el,el,ny});
		} else if (x < el) {
			int ny = min(y,static_rmq::query(x,el)+1);
			dij.push({d+el-x,el,ny});
		}
	}
	cout<<ans;
	
}


















詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

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

input:

1
1 1
1 1
0

output:

0

result:

ok single line: '0'

Test #2:

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

input:

2
1 1
1 500000001
1000000000 0

output:

500000000

result:

ok single line: '500000000'

Test #3:

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

input:

2
1 429578866
1 327150572
584071526 0

output:

102428294

result:

ok single line: '102428294'

Test #4:

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

input:

2
2 1
2 1
929403468 0

output:

0

result:

ok single line: '0'

Test #5:

score: 5
Accepted
time: 1ms
memory: 7908kb

input:

2
2 1
2 1
989240738 0

output:

0

result:

ok single line: '0'

Test #6:

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

input:

2
2 1
1 371562870
436620826 0

output:

65057958

result:

ok single line: '65057958'

Test #7:

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

input:

2
1 103853165
1 705401000
836091409 0

output:

130690412

result:

ok single line: '130690412'

Test #8:

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

input:

2
2 1
2 1
924491619 0

output:

0

result:

ok single line: '0'

Subtask #2:

score: 0
Time Limit Exceeded

Test #9:

score: 0
Time Limit Exceeded

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:


result:


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%