Submission #24936

#	Time	Username	Problem	Language	Result	Execution time	Memory
24936		zigui	케이크 (JOI13_cake)	C++14	100 / 100	779 ms	119188 KiB

cake

#include<stdio.h>
#include<assert.h>
#include<vector>
#include<string.h>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<string>
#include<iostream>
#include<set>
#include<unordered_set>
#include<map>
#include<queue>
#include<functional>
#include<list>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double, double> pdd;
typedef tuple<int,int,int> t3;

const int MX = 1<<19;
const int MM = 1000000007;

struct node{
	node(){}
	node(ll f, ll s, int c, int v):f(f), s(s), c(c), v(v){}
	ll f, s;
	int c, v;
};

node merge(node l, node r){
	if( l.c == 0 ) return node(l.f + r.f, l.s + r.s, l.c^r.c, min(l.v, r.v));
	return node(l.f + r.s, l.s + r.f, l.c^r.c, min(l.v, r.v));
}

struct Tree{
	node t[MX*2];
	node read(){ return t[1]; }
	void update(node n){
//		printf("update %d %d %d %d\n", n.f, n.s, n.c, n.v);
		int x = n.v + MX;
		t[x] = n;
		while(x > 1){
			x /= 2; t[x] = merge(t[x*2+1], t[x*2]);
		}
	}
	void remove(node n){
//		printf("remove %d %d %d %d\n", n.f, n.s, n.c, n.v);
		int x = n.v + MX;
		t[x] = node(0, 0, 0, x);
		while(x > 1){
			x /= 2; t[x] = merge(t[x*2+1], t[x*2]);
		}
	}
} tree;

vector<node> rm[MX], add[MX];
vector<int> X;
int N, M, a, b;
int D[MX], A[MX];
ll ans[MX], R[MX];

ll get_ans(int st){
	auto n = [](int s){ return s%N+1; };
	auto b = [](int s){ return (s+N-2)%N+1; };
	ll ans = D[st];
	int c = 1, l = b(st), r = n(st);
	while(l != r){
		int p = 0;
		if( D[l] < D[r] ) p = D[r], r = n(r);
		else p = D[l], l = b(l);
		if( !c ) ans += p;
		c ^= 1;
	}
	if( !c ) ans += D[l];
	return ans;
}

int main()
{
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) scanf("%d", D+i);

	int mn = 1;
	for(int i = 2; i <= N; i++) if( D[i] < D[mn] ) mn = i;
	ans[0] = get_ans(mn);
	for(int i = mn%N+1, j = 1; i != mn; i = i%N+1, j++) A[j] = D[i]; N--;

	for(int i = 1; i <= N; i++) X.push_back(A[i]);
	sort(X.begin(), X.end());
	auto t = [](vector<int> &X, int a){ return lower_bound(X.begin(), X.end(), a) - X.begin(); };
	
	vector<node> stack;
	for(int i = N; i >= 1; i--){
		int v = t(X, A[i]);
		node c = node(A[i], 0, 1, v);
		while( stack.size() && stack.back().v > v ){
			c = merge(c, stack.back());
			add[i].push_back(stack.back());
			tree.remove(stack.back());
			stack.pop_back();
		}
		stack.push_back(c);
		tree.update(c);
		rm[i].push_back(c);
	}

	stack.clear();
	for(int i = 1; i <= N; i++){
		for(node c : rm[i]) tree.remove(c);
		for(node c : add[i]) tree.update(c);
		ans[i] = tree.read().s + A[i];
		int v = t(X, A[i]);
		node c = node(A[i], 0, 1, v);
		while( stack.size() && stack.back().v > v ){
			c = merge(c, stack.back());
			add[i].push_back(stack.back());
			tree.remove(stack.back());
			stack.pop_back();
		}
		stack.push_back(c);
		tree.update(c);
	}
	for(int i = 0; i <= N; i++){
		R[(i+mn-1)%(N+1)] = ans[i] + (N%2 == 0 && i ? D[mn] : 0);
	}
	for(int i = 0; i <= N; i++) printf("%lld\n", R[i]);
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:85:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
cake.cpp:86:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= N; i++) scanf("%d", D+i);
                                              ^

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