Submission #341633

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
341633	2020-12-30T10:31:56 Z	tengiz05	Mountain Trek Route (IZhO12_route)	C++17	100 / 100	155 ms	49004 KB

route

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool ckmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool ckmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 1e6+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int a[N], n, m, k;
int l[N], r[N]; // left and right neighbors of the block
struct DSU{
	vector<int> sz, p;
	int numofsets;
	DSU(int nn){
		sz.assign(nn,1);
		p.assign(nn, 0);
		for(int i=0;i<nn;i++)p[i]=i;
	}
	int par(int u){
		if(p[u] == u)return u;
		return p[u] = par(p[u]);
	}
	void merge(int u, int v){
		u = par(u);v = par(v);
		if(u == v)return;
		numofsets--;
		p[v] = u;
		sz[u] += sz[v];
		r[u] = r[v];
		l[v] = l[u];
	}
	int size(int u){u = par(u);return sz[par(u)];}
}dsu(N);
int get(int u){
	return dsu.par(u);
}
void solve(int test_case){
	int i, j;
	cin >> n >> k;
	for(i=1;i<=n;i++){
		cin >> a[i];
	}
	dsu.numofsets = n;
	l[1] = n;
	r[1] = 2;
	l[n] = n-1;
	r[n] = 1;
	for(i=2;i<n;i++){
		l[i] = i-1;
		r[i] = i+1;
	}
	a[n+1] = a[1];
	a[0] = a[n];
	int answer = 0;
	for(i=1;i<=n;i++){
		if(a[i] == a[r[i]])dsu.merge(i, r[i]);
	}
	priority_queue<pii, vector<pii>, greater<pii>> q;
	vector<pii> tmp;
	for(i=1;i<=n;i++){
		if(dsu.par(i) == i && a[l[i]+1] < a[l[i]] && a[r[i]-1] < a[r[i]]){
			q.push({dsu.size(i),i});
			tmp.pb({dsu.size(i),i});
		}
	}
	//~ for(auto [x, y] : tmp)cout << x << ' ' << y << '\n';
	//~ cout << "\n\n";
	while(!q.empty()){
		auto [S, idx] = q.top();q.pop();
		i = get(idx);
		int mn = min(a[get(l[i])], a[get(r[i])]);
		if((mn-a[i])*S <= k){
			k -= (mn-a[i])*S;
			answer += 2*(mn-a[i]);
			a[i] += mn-a[i];
			if(a[i] == a[get(l[i])])dsu.merge(get(l[i]), i);
			if(a[i] == a[get(r[i])])dsu.merge(i, get(r[i]));
			i = get(i);
			mn = min(a[get(l[i])], a[get(r[i])]);
			if(mn > a[i])q.push({dsu.size(i), i});
		}else {
			answer += 2*(k/S);
			break;
		}
		//~ for(i=1;i<=n;i++){
			//~ cout << a[i] << ' ';
		//~ }cout << "\n\n";
	}
	cout << answer << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int _T;
	cin >> _T;
	for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message

route.cpp: In function 'void solve(long long int)':
route.cpp:45:9: warning: unused variable 'j' [-Wunused-variable]
   45 |  int i, j;
      |         ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	15980 KB	Output is correct
2	Correct	10 ms	15980 KB	Output is correct
3	Correct	10 ms	15980 KB	Output is correct
4	Correct	10 ms	15980 KB	Output is correct
5	Correct	10 ms	15980 KB	Output is correct
6	Correct	10 ms	15980 KB	Output is correct
7	Correct	10 ms	15980 KB	Output is correct
8	Correct	10 ms	15980 KB	Output is correct
9	Correct	10 ms	15980 KB	Output is correct
10	Correct	21 ms	18412 KB	Output is correct
11	Correct	24 ms	20192 KB	Output is correct
12	Correct	22 ms	18412 KB	Output is correct
13	Correct	155 ms	47084 KB	Output is correct
14	Correct	149 ms	49004 KB	Output is correct
15	Correct	126 ms	47052 KB	Output is correct
16	Correct	135 ms	48108 KB	Output is correct
17	Correct	145 ms	48236 KB	Output is correct
18	Correct	140 ms	49004 KB	Output is correct
19	Correct	139 ms	49004 KB	Output is correct
20	Correct	124 ms	45420 KB	Output is correct