Submission #1050774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050774		dozer	Candies (JOI18_candies)	C++14	100 / 100	357 ms	22388 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define sp " "
//#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define LL node * 2
#define RR node * 2 + 1
#define N 300005
#define ll long long
#define int long long

const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;


int a[N], pre[2][N];

int32_t main(){
	//fileio();
	fastio();


	int n;
	cin>>n;
	for (int i = 1; i <= n; i++){
		cin>>a[i];
		pre[0][i] = pre[0][i - 1], pre[1][i] = pre[1][i - 1];
		pre[i % 2][i] += a[i];
	}


	set<array<int, 3>> s;
	set<pii> ranges;
	int ans = 0;

	for (int i = 1; i <= n; i++)
		s.insert({a[i], i, 0});


	auto add_range = [&](int l, int r){
		ranges.insert({l, r});
		if (l == 1) return;
		int prv = pre[r % 2][r] - pre[r % 2][l - 1];
		int curr = pre[(r + 1) % 2][r + 1] - pre[(r + 1) % 2][l - 2];
		if (r < n) s.insert({curr - prv, l, r});
	};

	auto del_range = [&](int l, int r){
		ranges.erase({l, r});
		if (l == 1) return;
		
		int prv = pre[r % 2][r] - pre[r % 2][l - 1];
		int curr = pre[(r + 1) % 2][r + 1] - pre[(r + 1) % 2][l - 2];
		if (r < n) {
			s.erase({curr - prv, l, r});
		}
		
	};


	auto shift = [&](array<int, 3> x){
		ans += x[0];
		int l = x[1], r = x[2];
		if (r == 0){
			s.erase(x);
			r = l;
		}
		else{
			del_range(l, r);
			l--, r++;
		}

		if (l > 1){
			s.erase({a[l - 1], l - 1, 0});
		}
		if (r < n){
			s.erase({a[r + 1], r + 1, 0});
		}
		
		auto it = ranges.lower_bound({r, 0});
		if (it != ranges.end() && it->st == r + 2){
			pii tmp = *it;
			del_range(tmp.st, tmp.nd);
			r = tmp.nd;
		}

		it = ranges.lower_bound({r, 0});
		if (it != ranges.begin()){
			it--;
			if (it->nd == l - 2){
				pii tmp = *it;
				del_range(tmp.st, tmp.nd);
				l = tmp.st;
			}
		}


		add_range(l, r);
	};

	for (int j = 1; j <= (n + 1) / 2; j++){
		assert(!s.empty());
		array<int, 3> curr = *s.rbegin();
		shift(curr);
		cout<<ans<<endl;
	}

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

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