Submission #1053602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053602		n1k	Text editor (CEOI24_editor)	C++17	5 / 100	1 ms	348 KiB

Main

#include <bits/stdc++.h>

#if defined(LOCAL)
#include "debug.cpp"
#else
#define debug(x...) 0
#endif // LOCAL

using namespace std;

using ll = long long;

#define all(a) (a).begin(), (a).end()



struct Node{
	ll v = 1e15;
	Node(){};
	Node(ll _v){
		v=_v;
	}
};

void __print(Node n){
	cerr<<n.v;
}

void solve(){
	int n, sr, sc, er, ec; cin >> n >> sr >> sc >> er >> ec;
	sr--, sc--, er--, ec--;
	vector<ll> l(n), smin(n, 1e15);
	for(int i=0; i<n; i++) cin >> l[i];
	smin[er]=l[er];
	debug(smin);
	for(int r=er-1; r>=0; r--){
		smin[r]=min(smin[r+1], l[r]);
	}
	for(int r=er+1; r<n; r++){
		smin[r]=min(smin[r-1], l[r]);
	}

	vector<array<ll, 2>> save(n, {ll(1e15), ll(1e15)});
	map<int, Node> row;

	row[sc]=0;

	ll add = 0, ans = 1e15;

	auto clean = [&](int c1){
		if(not row.count(c1)) return;
		while(next(row.find(c1))!=row.end()){
			auto [c2, cost] = *next(row.find(c1));
			if(row[c1].v + c2 - c1 < cost.v){
				row.erase(next(row.find(c1)));
			}else{
				break;
			}
		}
		while(row.find(c1)!=row.begin()){
			auto [c2, cost] = *prev(row.find(c1));
			if(row[c1].v + c1 - c2 < cost.v){
				row.erase(prev(row.find(c1)));
			}else{
				break;
			}
		}
	};
	debug(er, ec);
	auto simup = [&](int startr, int endr=0){
		// simulate up
		for(int r=startr; r>endr; r--){
			// answer
			auto it = row.lower_bound({ec});
			if(it!=row.end()){
				ans = min(ans, abs(r - er) + abs(min(smin[r], ll(it->first)) - ec) + it->second.v + add);
			}
			if(it!=row.begin()){
				it--;
				ans = min(ans, abs(r - er) + abs(min(smin[r], ll(it->first)) - ec) + it->second.v + add);
			}

			debug(r, row, add);
			save[r][0] = min(save[r][0], row[0].v + add);
			save[r][1] = min(save[r][1], row[l[r]].v + add);
			row[0] = min(row[0].v, save[r][0] - add);
			row[l[r]] = min(row[l[r]].v, save[r][1] - add);

			clean(0); clean(l[r]);

			ll bc, cost;
			Node node;
			// anfange
			tie(bc, node) = *row.begin();
			cost = node.v;
			row[0] = min(row[0].v, cost + bc);
			// ende
			tie(bc, node) = *--row.end();
			cost=node.v;
			row[l[r]] = min(row[l[r]].v, cost + l[r] - bc);

			// anfange nach oben 
			// alle direkt nach oben
			while(row.size() and (--row.end())->first > l[r-1]){
				tie(bc, node) = *--row.end();
				cost=node.v;
				row[l[r-1]] = min(row[l[r-1]].v, cost);
				row.erase(--row.end());
			}
			row[l[r-1]] = min(row[l[r-1]].v, row[0].v);
			clean(0);
			clean(l[r-1]);
			add++;
		}
	};
	auto simdown = [&](int startr){
		// simulate down
		for(int r=startr; r+1<n; r++){

			auto it = row.lower_bound({ec});
			if(r==1 and it->first==7){
				debug(smin[r]);
			}
			if(it!=row.end()){
				ans = min(ans, abs(r - er) + abs(min(smin[r], ll(it->first)) - ec) + it->second.v + add);
			}
			if(it!=row.begin()){
				it--;
				ans = min(ans, abs(r - er) + abs(min(smin[r], ll(it->first)) - ec) + it->second.v + add);
			}

			debug(r, row, add);
			save[r][0] = min(save[r][0], row[0].v + add);
			save[r][1] = min(save[r][1], row[l[r]].v + add);

			row[0] = min(row[0].v, save[r][0] - add);
			row[l[r]] = min(row[l[r]].v, save[r][1] - add);

			clean(0); clean(l[r]);

			ll bc, cost;
			Node node;
			// anfange
			tie(bc, node) = *row.begin();
			cost=node.v;
			row[0] = min(row[0].v, cost + bc);
			// ende
			tie(bc, node) = *--row.end();
			cost=node.v;
			row[l[r]] = min(row[l[r]].v, cost + l[r] - bc);

			// ende nach unten

			// alle direkt nach untern 
			while(row.size() and (--row.end())->first > l[r+1]){
				tie(bc, node) = *--row.end();
				cost=node.v;
				row[l[r+1]] = min(row[l[r+1]].v, cost);
				row.erase(--row.end());
			}
			row[0] = min(row[0].v, row[l[r]].v);
			clean(0);
			clean(l[r+1]);
			add++;
		}
	};

	simup(sr);
	simdown(0);
	simup(n-1);
	simdown(0);
	simup(n-1, er);

	for(auto [cc, cost]:row){
		ans=min(ans, cost.v+add + abs(ec - cc));
	}

	cout << ans << endl;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int t=1; //cin >> t;
	while(t--) solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:6:21: warning: statement has no effect [-Wunused-value]
    6 | #define debug(x...) 0
      |                     ^
Main.cpp:35:2: note: in expansion of macro 'debug'
   35 |  debug(smin);
      |  ^~~~~
Main.cpp:6:21: warning: statement has no effect [-Wunused-value]
    6 | #define debug(x...) 0
      |                     ^
Main.cpp:69:2: note: in expansion of macro 'debug'
   69 |  debug(er, ec);
      |  ^~~~~
Main.cpp: In lambda function:
Main.cpp:6:21: warning: statement has no effect [-Wunused-value]
    6 | #define debug(x...) 0
      |                     ^
Main.cpp:83:4: note: in expansion of macro 'debug'
   83 |    debug(r, row, add);
      |    ^~~~~
Main.cpp: In lambda function:
Main.cpp:6:21: warning: statement has no effect [-Wunused-value]
    6 | #define debug(x...) 0
      |                     ^
Main.cpp:122:5: note: in expansion of macro 'debug'
  122 |     debug(smin[r]);
      |     ^~~~~
Main.cpp:6:21: warning: statement has no effect [-Wunused-value]
    6 | #define debug(x...) 0
      |                     ^
Main.cpp:132:4: note: in expansion of macro 'debug'
  132 |    debug(r, row, add);
      |    ^~~~~

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