Submission #1137726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137726		Jawad_Akbar_JJ	Text editor (CEOI24_editor)	C++20	5 / 100	4110 ms	466492 KiB

Main

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <algorithm>

using namespace std;
const int N = 6e6 + 10;
int l[N], Min[N];
int n, a, b, c, d, mx, cur = 1;
map<pair<int,int>,int> id;

void solve1(){
	if (a == c and b == d){
		cout<<0<<'\n';
		exit(0);
	}

	if (a == 1 and c == 1){
		int Ans = abs(d - b);
		if (b < d) Ans = min(Ans, 2 + l[1] + 1 - d);
		else Ans = min(Ans, 1 + d);
		cout<<Ans<<'\n';
	}
	else if (c == 2)
		cout<<1<<'\n';
	else
		cout<<min(d, l[1] + 1 - d + 1)<<'\n';
	exit(0);
}

int Mn[1005][5005], seen[1005][5005];
queue<pair<int,int>> Q;

void update(int i, int j, int c){
	if (i < 1 or i > n or j > l[i] + 1 or seen[i][j]) return;
	seen[i][j] = 1;
	Mn[i][j] = c;
	Q.push({i, j});
}

void bfs(){
	Q.push({a, b});
	seen[a][b] = 1;

	while (Q.size() > 0){
		auto [i, j] = Q.front();
		Q.pop();

		update(i - 1, min(j, l[i-1] + 1), Mn[i][j] + 1);
		update(i + 1, min(j, l[i+1] + 1), Mn[i][j] + 1);

		if (j == l[i] + 1) update(i + 1, 1, Mn[i][j] + 1);
		else update(i, j + 1, Mn[i][j] + 1);

		if (j == 1) update(i - 1, l[i-1] + 1, Mn[i][j] + 1);
		else update(i, j - 1, Mn[i][j] + 1);
	}
	cout<<Mn[c][d]<<'\n';
	exit(0);
}

vector<pair<int,int>> nei[N];

void Add(int i, int j, int w){
	nei[j].push_back({i, w});
}

void dijkstra(){
	for (int i=1;i<N;i++)
		Min[i] = 2e9;
	Min[id[{a, b}]] = 0;
	set<pair<int,int>> st = {{0, id[{a, b}]}};

	while (st.size() > 0){
		auto [W, u] = *begin(st);
		st.erase(begin(st));

		for (auto [i, w] : nei[u]){
			// cout<<u<<" "<<i<<" "<<w<<'\n';
			if (Min[i] > Min[u] + w){
				st.erase({Min[i], i});
				Min[i] = Min[u] + w;
				st.insert({Min[i], i});
			}
		}
	}
}

signed main(){
	cin>>n>>a>>b>>c>>d;


	map<int,int> seen;
	vector<int> vec = {b};
	if (d != b) vec = {b, d};
	seen[d] = seen[b] = 1;
	for (int i=1;i<=n;i++){
		cin>>l[i], mx = max(mx, l[i]);
		if (!seen[l[i] + 1]) vec.push_back(l[i] + 1);
		seen[l[i] + 1] = 1;
	}

	// if (n <= 2) solve1();
	// if (n <= 1000 and mx <= 5000) bfs();

	sort(begin(vec), end(vec));

	for (int i=1;i<=n;i++){
		for (int j : vec){
			if (j > l[i] + 1) break;
			id[{i, j}] = cur++;
		}
	}
	for (int i=1;i<=n;i++){
		for (int k=0;k<vec.size();k++){
			int j = vec[k];
			if (j > l[i] + 1) break;

			if (i != 1 and l[i-1] + 1 >= j) Add(id[{i-1, j}], id[{i, j}], 1);
			if (i != n) Add(id[{i+1, min(j, l[i+1] + 1)}], id[{i, j}], 1);

			if (k == 0){
				if (i != 1)
					Add(id[{i - 1, l[i-1] + 1}], id[{i, j}], 1);
			}
			else{
				Add(id[{i, vec[k-1]}], id[{i, j}], vec[k] - vec[k - 1]);
			}

			if (k == vec.size() - 1){
				if (i != n)
					Add(id[{i + 1, 1}], id[{i, j}], 1);
			}
			else{
				Add(id[{i, vec[k+1]}], id[{i, j}], vec[k + 1] - j);
			}
		}
	}
	dijkstra();
	cout<<Min[id[{c, d}]]<<'\n';
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 26
• Subtask 4: 0 / 11
• Subtask 5: 0 / 44