Submission #24936

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
24936	2017-06-17T12:11:31 Z	zigui	케이크 (JOI13_cake)	C++14	100 / 100	779 ms	119188 KB

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

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	64000 KB	Output is correct
2	Correct	9 ms	64272 KB	Output is correct
3	Correct	9 ms	64144 KB	Output is correct
4	Correct	9 ms	64000 KB	Output is correct
5	Correct	6 ms	64172 KB	Output is correct
6	Correct	13 ms	64000 KB	Output is correct
7	Correct	9 ms	64000 KB	Output is correct
8	Correct	13 ms	64000 KB	Output is correct
9	Correct	6 ms	63464 KB	Output is correct
10	Correct	6 ms	63464 KB	Output is correct
11	Correct	6 ms	63464 KB	Output is correct

Subtask #2

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	203 ms	73704 KB	Output is correct
2	Correct	159 ms	73844 KB	Output is correct
3	Correct	183 ms	74032 KB	Output is correct
4	Correct	566 ms	88196 KB	Output is correct
5	Correct	493 ms	84236 KB	Output is correct
6	Correct	629 ms	95160 KB	Output is correct
7	Correct	609 ms	102388 KB	Output is correct
8	Correct	733 ms	95328 KB	Output is correct
9	Correct	779 ms	95160 KB	Output is correct
10	Correct	446 ms	119188 KB	Output is correct
11	Correct	566 ms	97452 KB	Output is correct
12	Correct	516 ms	96716 KB	Output is correct
13	Correct	473 ms	102924 KB	Output is correct
14	Correct	396 ms	104320 KB	Output is correct
15	Correct	549 ms	95832 KB	Output is correct