oj.uz

Submission #198544

# Submission time Handle Problem Language Result Execution time Memory
198544 2020-01-26T14:19:46 Z gs18081 Candies (JOI18_candies) C++11
0 / 100
 7 ms 760 KB 
#include <bits/stdc++.h>

using namespace std;
	
typedef long long int ll;
typedef pair<ll,int> pli;
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];
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;
		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

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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 760 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Correct 7 ms 632 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 7 ms 632 KB Output is correct
6 Correct 7 ms 632 KB Output is correct
7 Correct 7 ms 632 KB Output is correct
8 Correct 7 ms 632 KB Output is correct
9 Correct 7 ms 632 KB Output is correct
10 Correct 7 ms 636 KB Output is correct
11 Incorrect 7 ms 632 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 760 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Correct 7 ms 632 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 7 ms 632 KB Output is correct
6 Correct 7 ms 632 KB Output is correct
7 Correct 7 ms 632 KB Output is correct
8 Correct 7 ms 632 KB Output is correct
9 Correct 7 ms 632 KB Output is correct
10 Correct 7 ms 636 KB Output is correct
11 Incorrect 7 ms 632 KB Output isn't correct
12 Halted 0 ms 0 KB -