Submission #1073967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073967		GrindMachine	Text editor (CEOI24_editor)	C++17	56 / 100	2219 ms	1048576 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define conts continue
#define sz(a) (int)a.size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &x, T y){
	x = min(x,y);
}

template<typename T>
void amax(T &x, T y){
	x = max(x,y);
}

template<typename A,typename B>
string to_string(pair<A,B> p);

string to_string(const string &s){
	return "'"+s+"'";
}

string to_string(const char* s){
	return to_string((string)s);
}

string to_string(bool b){
	return b?"true":"false";
}

template<typename A>
string to_string(A v){
	string res = "{";
	trav(x,v){
		res += to_string(x)+",";
	}
	if(res.back() == ',') res.pop_back();
	res += "}";
	return res;
}

template<typename A,typename B>
string to_string(pair<A,B> p){
	return "("+to_string(p.ff)+","+to_string(p.ss)+")";
}

#define debug(x) cout << "[" << #x << "]: "; cout << to_string(x) << endl

const int MOD = 1e9 + 7;
const int N = 1e3 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = (ll)1e18 + 5;

void solve(int test_case){
	ll n; cin >> n;
	ll si,sj,ei,ej; cin >> si >> sj >> ei >> ej;
	vector<ll> a(n+5);
	rep1(i,n) cin >> a[i];

	vector<ll> b;
	rep1(i,n) b.pb(a[i]+1);
	b.pb(sj), b.pb(ej);
	b.pb(1);
	b.pb(-1);
	sort(all(b));
	b.resize(unique(all(b))-b.begin());

	ll m = sz(b)-1;
	vector<ll> ind(n+5);

	vector<array<ll,3>> adj[n+5][m+5];

	// left/right
	rep1(i,n){
		// within row
		ll pos = 1;
		for(int j = 2; j <= m; ++j){
			if(b[j] > a[i]+1) break;
			pos = j;
			ll w = b[j]-b[j-1];
			adj[i][j-1].pb({i,j,w});
			adj[i][j].pb({i,j-1,w});
		}

		ind[i] = pos;

		// across row
		if(i+1 <= n){
			ll j = ind[i];
			adj[i][j].pb({i+1,1,1});
			adj[i+1][1].pb({i,j,1});
		}
	}

	// up/down
	rep1(i,n){
		rep1(j,ind[i]){
			// go up
			if(i-1 >= 1){
				ll j2 = min((ll)j,ind[i-1]);
				adj[i][j].pb({i-1,j2,1});
			}

			// go down
			if(i+1 <= n){
				ll j2 = min((ll)j,ind[i+1]);
				adj[i][j].pb({i+1,j2,1});
			}
		}
	}

	sj = lower_bound(all(b),sj)-b.begin();
	ej = lower_bound(all(b),ej)-b.begin();

	priority_queue<array<ll,3>,vector<array<ll,3>>,greater<array<ll,3>>> pq;
	bool vis[n+5][m+5];
	memset(vis,0,sizeof vis);

	auto ins = [&](ll i, ll j, ll cost){
		pq.push({cost,i,j});
	};

	ins(si,sj,0);

	while(!pq.empty()){
		auto [cost,i,j] = pq.top();
		pq.pop();

		if(vis[i][j]) conts;
		vis[i][j] = 1;

		if(i == ei and j == ej){
			cout << cost << endl;
			return;
		}

		for(auto [i2,j2,w] : adj[i][j]){
			ins(i2,j2,cost+w);
		}
	}

	assert(0);
}

int main(){
	fastio;

	int t = 1;
	// cin >> t;

	rep1(i,t){
		solve(i);
	}

	return 0;
}

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