답안 #24936

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
24936 2017-06-17T12:11:31 Z zigui 케이크 (JOI13_cake) C++14
100 / 100
779 ms 119188 KB
#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);
                                              ^
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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