Submission #335003

#	Time	Username	Problem	Language	Result	Execution time	Memory
335003		Plurm	Candies (JOI18_candies)	C++11	100 / 100	873 ms	29892 KiB

candies

#include <bits/stdc++.h>
using namespace std;
int a[200005];
struct state{
	int u, v;
	long long nw, ow;
	state(int x, int y, long long z, long long t) : u(x), v(y), nw(z), ow(t) {}
	friend bool operator<(const state& x, const state& y){
		if(x.nw - x.ow != y.nw - y.ow) return x.nw - x.ow < y.nw - y.ow;
		return make_pair(x.u, x.v) < make_pair(y.u, y.v);
	}
};
set<pair<int,int> > ranges; // picked ranges
set<pair<int,int> > options; // potential options (sorted by pair)
set<state> states; // potential options
set<pair<int,int> >::iterator isCovered(int x){
	// checks whether x is covered?
	auto it = ranges.upper_bound(make_pair(x, 1000000));
	if(it == ranges.begin()) return ranges.end();
	it--;
	return it->second >= x ? it : ranges.end();
}
set<pair<int,int> >::iterator isOptionsCovered(int x){
	// checks whether x is covered?
	auto it = options.upper_bound(make_pair(x, 1000000));
	if(it == options.begin()) return options.end();
	it--;
	return it->second >= x ? it : options.end();
}
long long qs[200005];
long long qsx[200005];
inline long long getSum(int idx){
	return idx > 0 ? qsx[idx] : 0ll;
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1; i <= n; i++){
		scanf("%d",a+i);
		states.emplace(i,i,a[i],0);
		options.emplace(i,i);
		qsx[i] = (i-2 > 0 ? qsx[i-2] : 0ll) + a[i];
		qs[i] = qs[i-1] + a[i];
	}
	long long ans = 0ll;
	for(int turn = 1;  turn <= (n+1)/2; turn++){
		auto cur = *states.rbegin(); // maximum potential weight
		ans += cur.nw - cur.ow;
		states.erase(cur);
		options.erase(make_pair(cur.u, cur.v));
		if(ranges.count(make_pair(cur.u+1, cur.v-1)))
			ranges.erase(make_pair(cur.u+1, cur.v-1));

		// left-joinable and right-joinable?
		auto lchk = cur.u > 1 ? isCovered(cur.u - 2) : ranges.end();
		auto rchk = cur.v < n ? isCovered(cur.v + 2) : ranges.end();
		int targetL = lchk == ranges.end() ? cur.u : lchk->first;
		int targetR = rchk == ranges.end() ? cur.v : rchk->second;
		if(lchk != ranges.end()){
			ranges.erase(lchk);
		}
		auto p = isOptionsCovered(cur.u-1);
		// find the props of the state
		if(p != options.end()){
			long long nw = getSum(p->second) - getSum(p->first - 2);
			long long ow = qs[p->second] - qs[p->first-1] - nw;
			state ex(p->first, p->second, nw, ow);
			states.erase(ex);
			options.erase(p);
		}
		if(rchk != ranges.end()){
			ranges.erase(rchk);
		}
		p = isOptionsCovered(cur.v+1);
		if(p != options.end()){
			// find the props of the state
			long long nw = getSum(p->second) - getSum(p->first - 2);
			long long ow = qs[p->second] - qs[p->first-1] - nw;
			state ex(p->first, p->second, nw, ow);
			states.erase(ex);
			options.erase(p);
		}
		ranges.emplace(targetL, targetR);
		if(targetL-1 >= 1 && targetR+1 <= n){
			options.emplace(targetL-1, targetR+1);
			long long cow = getSum(targetR) - getSum(targetL-2);
			states.emplace(targetL-1, targetR+1, qs[targetR+1] - qs[targetL-2] - cow, cow);
		}
		printf("%lld\n", ans);
	}
	//printf("RANGES\n");
	for(auto r : ranges){
		//printf("%d %d\n", r.first, r.second);
	}
	//printf("OPTIONS\n");
	for(auto r : options){
		//printf("%d %d\n", r.first, r.second);
	}
	//printf("STATES\n");
	for(auto r : states){
		//printf("%d %d\n", r.u, r.v);
	}
	//printf("===\n");
	return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:92:11: warning: variable 'r' set but not used [-Wunused-but-set-variable]
   92 |  for(auto r : ranges){
      |           ^
candies.cpp:96:11: warning: variable 'r' set but not used [-Wunused-but-set-variable]
   96 |  for(auto r : options){
      |           ^
candies.cpp:100:11: warning: variable 'r' set but not used [-Wunused-but-set-variable]
  100 |  for(auto r : states){
      |           ^
candies.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
candies.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |   scanf("%d",a+i);
      |   ~~~~~^~~~~~~~~~

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