Submission #198553

#	Time	Username	Problem	Language	Result	Execution time	Memory
198553		gs18081	Candies (JOI18_candies)	C++11	100 / 100	396 ms	25976 KiB

candies

#include <bits/stdc++.h>

using namespace std;
	
typedef long long int ll;
typedef pair<int,int> pii;
typedef tuple<ll,int,int,int> ti;

const int MAXN = 202020;

struct UF{
	int n;
	vector<int> prt;
	vector<int> s;
	vector<int> e;
	UF(){}
	void resize(int size){
		n = size;
		prt = vector<int> (n+1,0);
		s = vector<int> (n+1,0);
		e = vector<int> (n+1,0);
		for(int i=1;i<=n;i++){
			s[i] = e[i] = prt[i] = i;
		}
	}
	int findprt(int node){
		if(prt[node] == node) return node;
		return prt[node] = findprt(prt[node]);
	}
	void merge(int a,int b){
		a = findprt(a); b = findprt(b);
		s[a] = min(s[a],s[b]);
		e[a] = max(e[a],e[b]);
		prt[b] = a;
	}
	pii getrange(int num){
		num = findprt(num);
		return pii(s[num],e[num]);
	}
}uf;

int N;
ll arr[MAXN];
ll sum[MAXN];
ll hsum[MAXN];
ll zsum[MAXN];
int vis[MAXN];
set<ti> st;
ll now = 0;

int main(){
	scanf("%d",&N);
	uf.resize(N);
	for(int i=1;i<=N;i++){
		scanf("%lld",&arr[i]);
	}
	for(int i=1;i<=N;i++){
		sum[i] = arr[i] + sum[i-1];
		hsum[i] = hsum[i-1];
		zsum[i] = zsum[i-1];
		if(i & 1) hsum[i] += arr[i];
		else zsum[i] += arr[i];
		st.insert(ti(arr[i],i,i,i));
	}
	while(!st.empty()){
		auto it = st.end();
		it--;
		ll c;
		int num;
		int s,e;
		tie(c,num,s,e) = *it;
		st.erase(it);
		int ts,te;
		tie(ts,te) = uf.getrange(num);
		if(s != ts || e != te) continue;
		if(vis[s] || vis[e]) continue;
		vis[s] = 1;
		vis[e] = 1;
		now += c;
		int flag = 0;
		if(s != 1){
			uf.merge(num,s - 1);
			flag = 1;
		}
		if(e != N) {
			uf.merge(num,e + 1);
			flag = 1;
		}
		tie(s,e) = uf.getrange(num);
		if(flag && (s + e) % 2 == 0){
			ll sum = 0;
			if(s & 1) {
				sum = hsum[e] - hsum[s-1] - (zsum[e-1] - zsum[s]);
			}
			else {
				sum = zsum[e] - zsum[s-1] - (hsum[e-1] - hsum[s]);
			}
			st.insert(ti(sum,s,s,e));
		}
		printf("%lld\n",now);
	}
	return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
candies.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&arr[i]);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92