oj.uz

답안 #341633

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
341633 2020-12-30T10:31:56 Z tengiz05 등산 경로 (IZhO12_route) C++17
100 / 100
 155 ms 49004 KB 
#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

# 결과 실행 시간 메모리 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