oj.uz

Submission #295212

# Submission time Handle Problem Language Result Execution time Memory
295212 2020-09-09T14:24:30 Z 임성재(#5809) 케이크 (JOI13_cake) C++17
100 / 100
 770 ms 54488 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int n;
int sft;
deque<int> dQ;
vector<int> com;
vector<pair<pll, int>> st, ST, er[300010];
pll tree[1200010];
ll tot;
ll ans[300010];

void update(int node, int s, int e, int i, pll x) {
	if(s == e) {
		tree[node] = x;
		return;
	}

	int m = s + e >> 1;
	if(i <= m) update(node*2, s, m, i, x);
	else update(node*2+1, m+1, e, i, x);

	tree[node].fi = tree[node*2].fi + tree[node*2+1].fi;
	tree[node].se = tree[node*2+1].se;
	if(tree[node*2+1].fi & 1) tree[node].se -= tree[node*2].se;
	else tree[node].se += tree[node*2].se;
}

ll cal() {
	int p1 = 0, p2 = n-2;
	int c = 1;
	ll cnt[2] = {};
	cnt[0] = com[dQ[n-1]];

	while(p1 <= p2) {
		if(dQ[p1] >= dQ[p2]) cnt[c] += com[dQ[p1++]];
		else cnt[c] += com[dQ[p2--]];

		c = 1 - c;
	}

	return cnt[0];
}

int main() {
	fast;

	cin >> n;

	for(int i=0; i<n; i++) {
		int a;
		cin >> a;
		tot += a;
		dQ.eb(a);
		com.eb(a);
	}

	sort(all(com));
	com.erase(unique(all(com)), com.end());

	for(int i=0; i<n; i++) {
		dQ[i] = lower_bound(all(com), dQ[i]) - com.begin();
	}

	while(dQ[n-1]) {
		dQ.eb(dQ[0]);
		dQ.pop_front();
		sft++;
	}

	update(1, 0, com.size(), 0, mp(1, com[0]));

	for(int i=n-2; i>=0; i--) {
		ll sum = com[dQ[i]];
		int cnt = 1;
		while(st.size() && st.back().se > dQ[i]) {
			if(cnt & 1) sum -= st.back().fi.se;
			else sum += st.back().fi.se;
			
			cnt += st.back().fi.fi;
			
			er[i].eb(st.back());
			update(1, 0, com.size(), st.back().se, mp(0, 0));
			st.pop_back();
		}
		
		st.eb(mp(cnt, sum), dQ[i]);
		update(1, 0, com.size(), dQ[i], mp(cnt, sum));
	}

	for(int i=0; i<n-1; i++) {
		update(1, 0, com.size(), st.back().se, mp(0, 0));
		st.pop_back();
		reverse(all(er[i]));
		for(auto j : er[i]) {
			st.eb(j);
			update(1, 0, com.size(), j.se, j.fi);
		}

		ans[i] = (tot + com[dQ[i]] - tree[1].se) / 2;

		ll sum = com[dQ[i]];
		int cnt = 1;
		while(ST.size() && ST.back().se > dQ[i]) {
			if(cnt & 1) sum -= ST.back().fi.se;
			else sum += ST.back().fi.se;
			
			cnt += ST.back().fi.fi;
			update(1, 0, com.size(), ST.back().se, mp(0, 0));
			ST.pop_back();
		}
		
		ST.eb(mp(cnt, sum), dQ[i]);
		update(1, 0, com.size(), dQ[i], mp(cnt, sum));
	}

	ans[n-1] = cal();

	for(int i=0; i<n; i++) {
		cout << ans[(i + n - sft) % n] << " ";
	}
}

Compilation message

cake.cpp: In function 'void update(int, int, int, int, pll)':
cake.cpp:33:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |  int m = s + e >> 1;
      |          ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8064 KB Output is correct
2 Correct 12 ms 8256 KB Output is correct
3 Correct 12 ms 8064 KB Output is correct
4 Correct 13 ms 8064 KB Output is correct
5 Correct 14 ms 8064 KB Output is correct
6 Correct 14 ms 8064 KB Output is correct
7 Correct 13 ms 8320 KB Output is correct
8 Correct 12 ms 8064 KB Output is correct
9 Correct 6 ms 7424 KB Output is correct
10 Correct 5 ms 7424 KB Output is correct
11 Correct 5 ms 7552 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 18928 KB Output is correct
2 Correct 172 ms 19164 KB Output is correct
3 Correct 187 ms 19056 KB Output is correct
4 Correct 608 ms 32232 KB Output is correct
5 Correct 469 ms 30316 KB Output is correct
6 Correct 640 ms 46060 KB Output is correct
7 Correct 520 ms 49172 KB Output is correct
8 Correct 686 ms 45924 KB Output is correct
9 Correct 770 ms 45796 KB Output is correct
10 Correct 466 ms 50520 KB Output is correct
11 Correct 584 ms 46948 KB Output is correct
12 Correct 514 ms 50020 KB Output is correct
13 Correct 508 ms 47828 KB Output is correct
14 Correct 425 ms 54488 KB Output is correct
15 Correct 534 ms 47368 KB Output is correct