Submission #341632

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
341632	2020-12-30T10:31:29 Z	tengiz05	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	38 ms	11884 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 = 2e5+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});
		}
	}
	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;
		}
	}
	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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3436 KB	Output is correct
2	Correct	2 ms	3436 KB	Output is correct
3	Correct	3 ms	3436 KB	Output is correct
4	Correct	2 ms	3436 KB	Output is correct
5	Correct	2 ms	3436 KB	Output is correct
6	Correct	2 ms	3436 KB	Output is correct
7	Correct	2 ms	3436 KB	Output is correct
8	Correct	2 ms	3564 KB	Output is correct
9	Correct	2 ms	3564 KB	Output is correct
10	Correct	15 ms	6636 KB	Output is correct
11	Correct	18 ms	8672 KB	Output is correct
12	Correct	15 ms	6764 KB	Output is correct
13	Runtime error	38 ms	11884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Halted	0 ms	0 KB	-