Submission #1134643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134643		Nurislam	Text editor (CEOI24_editor)	C++17	0 / 100	0 ms	328 KiB

Main

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp> 
  
using namespace std;
//using namespace __gnu_pbds; 
  
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ff first
#define ss second
#define pb push_back
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
//#define ordered_met tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
 
template<class T, class U> inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmax(T& a, const U& b) { if (a < b) { a = b; return true; } return false; }
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)

const int mod = 1e9+7, inf = 1e18, mxn = 3e5;

void solve(){
	int n;
	cin >> n;
	array<int,2> s, f;
	for(int &i:s){cin >> i;i--;}
	for(int &i:f){cin >> i;i--;}
	
	
	vector<int> len(n);
	for(int &i:len) cin >> i;
	
	vector<int> mf(n, inf);
	mf[f[0]] = len[f[0]];
	for(int i = f[0]+1; i < n; i++)mf[i] = min(mf[i-1], len[i]);
	for(int i = f[0]-1; i >=0; i--)mf[i] = min(mf[i+1], len[i]);
	
	vector<int> mn(n, inf);
	mn[s[0]] = len[s[0]];
	for(int i = s[0]+1; i < n; i++)mn[i] = min(mn[i-1], len[i]);
	for(int i = s[0]-1; i >=0; i--)mn[i] = min(mn[i+1], len[i]);
	
	int ans = inf;
	if(mn[f[0]] >= len[f[0]]){
		ans = abs(f[0] - s[0]) + abs(f[1] - s[1]);
	}
	chmin(ans, abs(f[0] - s[0]) + abs(f[1] - mn[f[0]]));
	//cout << ans << '\n';
	
	vector<array<int,2> > dp(n, {inf,inf});
	priority_queue<array<int,3>, vector<array<int,3>>, greater<array<int,3>>> pq;
	for(int i = 0; i < n; i++){
		dp[i][1] = abs(i - s[0]) + abs(mn[i] - len[i]);
		dp[i][0] = abs(i - s[0]) + mn[i];
		pq.push({dp[i][1], i, 1});
		pq.push({dp[i][0], i, 0});
	}
	
	while(!pq.empty()){
		auto [dis, i, tp] = pq.top();
		pq.pop();
		if(dis > dp[i][tp])continue;
		
		if(tp == 1){
			chmin(ans, dis + abs(i - f[0]) + abs(len[i] - mf[i]) + abs(f[1] - mf[i]));
			if(i+1 < n && chmin(dp[i+1][0], dis + 1))
				pq.push({dp[i+1][0], i+1, 0});
		}else{
			
			chmin(ans, abs(i-f[0]) + f[1] + dis);
			if(i-1)chmin(ans, dis + 1 + abs(i- f[0]) + abs(len[i] - mf[i]) + abs(f[1] - mf[i]));
			
			if(i-1 >= 0 && chmin(dp[i-1][1], dis + 1))
				pq.push({dp[i-1][1], i-1, 1});
				
			if(i+1 < n && chmin(dp[i+1][0], dis + 1))
				pq.push({dp[i-1][0], i+1, 0});
				
			if(i-1 >= 0 && chmin(dp[i-1][0], dis + 1))
				pq.push({dp[i+1][0], i-1, 0});
		}
	}
	
	cout << ans << '\n';
};

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	};
}

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