Submission #338224

#	Time	Username	Problem	Language	Result	Execution time	Memory
338224		Kerim	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	1 ms	512 KiB

route

#include "bits/stdc++.h"
#define MAXN 1000009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int arr[MAXN],l[MAXN],r[MAXN],ata[MAXN],sz[MAXN];
int tap(int x){
	if(ata[x]==x)return x;
	return ata[x]=tap(ata[x]);	
}
void merge(int x,int y){
	if((x=tap(x))==(y=tap(y)))
		return;
	ata[x]=y;l[y]=l[x];sz[y]++;	
}
int main(){
    //freopen("file.in", "r", stdin);
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    	scanf("%d",arr+i);
    for(int i=1;i<=n;i++){
    	ata[i]=i,sz[i]=1;
    	if(i>1) l[i]=i-1;
		else l[i]=n;
		if(i<n)	r[i]=i+1;
		else r[i]=1;
    }
    for(int i=1;i<=n;i++)
    	if(arr[i]==arr[r[i]])
    		merge(i,r[i]);
    priority_queue<PII>q;
    for(int i=1;i<=n;i++)
    	if(ata[i]==i and arr[i]<min(arr[l[i]],arr[r[i]]))
    		q.push(mp(sz[i],i));
	ll ans=0;
	while(!q.empty()){
		int nd=q.top().ss;q.pop();
		int val=min(arr[tap(l[nd])],arr[tap(r[nd])])-arr[nd];
		if(val*1LL*sz[nd]>=k){
			ans+=2LL*(k/sz[nd]);
			break;
		}
		ans+=2LL*val;
		k-=sz[nd]*val;
		arr[nd]+=val;
		if(arr[nd]==arr[tap(l[nd])]) merge(l[nd],nd);
		if(arr[nd]==arr[tap(r[nd])]) merge(nd,r[nd]);
		nd=tap(nd);
		if(arr[nd]<min(arr[tap(l[nd])],arr[tap(r[nd])]))
			q.push(mp(sz[nd],nd));
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

route.cpp: In function 'int main()':
route.cpp:47:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   47 |     for(int i=1;i<=n;i++)
      |     ^~~
route.cpp:50:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   50 |  ll ans=0;
      |  ^~
route.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
route.cpp:35:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |      scanf("%d",arr+i);
      |      ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 100