Submission #1189345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189345		JooDdae	케이크 (JOI13_cake)	C++20	100 / 100	513 ms	76400 KiB

cake

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define mid ((l+r) >> 1)

struct block {
	ll s[2];
	int sz, L, R;
	block operator + (const block &a) const {
		int c = a.sz % 2;
		return {{s[c]+a.s[0], s[!c]+a.s[1]}, sz+a.sz, L, a.R};
	}
} o, t[1200120];

int n, a[300300], b[300300], r[300300];
ll ans[300300];

void update(int id, block &x, int node = 1, int l = 1, int r = n) {
	if(id < l || r < id) return;
	if(l == r) {
		t[node] = x;
		return;
	}
	update(id, x, node*2, l, mid), update(id, x, node*2+1, mid+1, r);
	t[node] = t[node*2] + t[node*2+1];
}

block find(int nl, int nr, int node = 1, int l = 1, int r = n) {
	if(r < nl || nr < l) return o;
	if(nl <= l && r <= nr) return t[node];
	return find(nl, nr, node*2, l, mid) + find(nl, nr, node*2+1, mid+1, r);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	iota(r+1, r+1+n, 1);
	sort(r+1, r+1+n, [&](auto x, auto y){ return a[x] < a[y]; });
	for(int i=1;i<=n;i++) b[r[i]] = i;

	int mn = r[1];
	rotate(a+1, a+mn, a+1+n), rotate(b+1, b+mn, b+1+n);
	
	ans[1] = a[1];
	for(int i=2, L = 2, R = n;i<=n;i++) {
		int C = a[L] > a[R] ? a[L++] : a[R--];
		if(i % 2) ans[1] += C;
	}

	vector<vector<block>> op(n+1);
	vector<block> st(1, o);
	for(int i=n;i>1;i--) {
		block u = {{a[i], 0}, 1, b[i], b[i]};
		while(st.back().L > b[i]) {
			auto P = st.back(); st.pop_back();
			op[i].push_back(P);
			update(P.L, o);
			int c = u.sz % 2;
			u.s[0] += P.s[c], u.s[1] += P.s[!c];
			u.sz += P.sz, u.R = P.R;
		}
		update(b[i], u);
		st.push_back(u);
	}

	st = {o};
	for(int i=2;i<=n;i++) {
		update(b[i], o);
		for(auto B : op[i]) update(B.L, B);
		
		ans[i] = t[1].s[1] + a[i] + (n%2 ? a[1] : 0);
		
		block u = {{a[i], 0}, 1, b[i], b[i]};
		while(st.back().R > b[i]) {
			auto P = st.back(); st.pop_back();
			update(P.R, o);
			int c = u.sz % 2;
			u.s[0] += P.s[c], u.s[1] += P.s[!c];
			u.sz += P.sz, u.L = P.L;
		}
		update(b[i], u);
		st.push_back(u);
	}

	for(int i=0;i<n;i++) cout << ans[(i-mn+1+n)%n+1] << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90