Submission #24933

#	Time	Username	Problem	Language	Result	Execution time	Memory
24933		dotorya	케이크 (JOI13_cake)	C++14	100 / 100	923 ms	93584 KiB

cake

#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size())  
#define rep(i, n) for(int i=0;i<n;i++)  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;

int in[300050];

int in2[300050];
int L[300050];
int R[300050];
ll sum1[300050];
ll sum2[300050];

class Node {
public:
	ll s1, s2;
	bool chk;
	Node() {
		*this = Node(0, 0, false);
	}
	Node(ll s1, ll s2, bool chk) : s1(s1), s2(s2), chk(chk) {}
};
Node operator + (Node a, Node b) {
	swap(a, b);
	Node rv;
	if (!a.chk) {
		rv.s1 = a.s1 + b.s1;
		rv.s2 = a.s2 + b.s2;
		rv.chk = b.chk;
	}
	else {
		rv.s1 = a.s1 + b.s2;
		rv.s2 = a.s2 + b.s1;
		rv.chk = !b.chk;
	}
	return rv;
}
vector <pii> V1;
vector <pii> V2;

vector <pii> Vx;
Node val[600050];
int ch(pii x) {
	int st = 0, en = (int)Vx.size() - 1, mi, rv = 0;
	while (st <= en) {
		mi = (st + en) / 2;
		if (mp(in2[Vx[mi].first], Vx[mi]) <= mp(in2[x.first], x)) {
			rv = mi;
			st = mi + 1;
		}
		else en = mi - 1;
	}
	return rv;
}

Node indt[2100000];
void update(int p, Node v) {
	p += IT_MAX;
	indt[p] = v;
	for (p /= 2; p; p /= 2) indt[p] = indt[2 * p] + indt[2 * p + 1];
}

ll ans[300050];
int main() {
	int N, i;
	scanf("%d", &N);
	for (i = 0; i < N; i++) scanf("%d", &in[i]);

	int mnp = 0;
	for (i = 1; i < N; i++) if (in[mnp] > in[i]) mnp = i;
	for (i = 1; i < N; i++) in2[i] = in[(mnp + i) % N];

	vector <pii> Vu;
	for (i = N - 1; i >= 1; i--) {
		while (!Vu.empty()) {
			if (Vu.back().first < in2[i]) break;
			Vu.pop_back();
		}
		if (!Vu.empty()) R[i] = Vu.back().second;
		else R[i] = N;
		Vu.emplace_back(in2[i], i);
	}

	for (i = 1; i < N; i++) {
		while (!V1.empty()) {
			int t = V1.back().first;
			if (in2[t] < in2[i]) break;
			V1.pop_back();
		}
		int st = 1;
		if (!V1.empty()) st = V1.back().first + 1;
		Vx.emplace_back(i, st);
		V1.emplace_back(i, st);
	}
	for (i = N - 1; i >= 1; i--) {
		while (!V2.empty()) {
			int t = V2.back().first;
			if (in2[t] < in2[i]) break;
			V2.pop_back();
		}

		int en = N - 1;
		if (!V2.empty()) en = V2.back().first - 1;
		Vx.emplace_back(i, en);
		V2.emplace_back(i, en);
	}
	sort(all(Vx), [](pii a, pii b) {
		if(in2[a.first] != in2[b.first]) return in2[a.first] < in2[b.first];
		else return a < b;
	});
	Vx.erase(unique(all(Vx)), Vx.end());
	for (i = 1; i < N; i++) {
		sum1[i] = sum1[i - 1] + in2[i];
		sum2[i] = (i == 1 ? 0 : sum2[i - 2]) + in2[i];
	}
	for (i = 0; i < Vx.size(); i++) {
		pii u = Vx[i];
		if (u.first >= u.second) {
			val[i].s1 = sum2[u.first];
			if (u.second % 2 == u.first % 2) {
				if (u.second != 1) val[i].s1 -= sum2[u.second - 2];
			}
			else val[i].s1 -= sum2[u.second - 1];
			val[i].s2 = (sum1[u.first] - sum1[u.second - 1]) - val[i].s1;
		}
		else {
			val[i].s2 = sum2[u.second];
			if (u.second % 2 == u.first % 2) {
				if (u.first != 1) val[i].s2 -= sum2[u.first - 2];
			}
			else val[i].s2 -= sum2[u.first - 1];
			val[i].s1 = (sum1[u.second] - sum1[u.first - 1]) - val[i].s2;
			if (u.first % 2 == u.second % 2) swap(val[i].s1, val[i].s2);
		}
		val[i].chk = (u.first % 2 == u.second % 2);
	}

	IT_MAX = 1 << 20;
	V1.clear();
	for (auto it : V2) {
	//	printf("%d\n", ch(it));
		update(ch(it), val[ch(it)]);
	}
	for (i = 1; i < N; i++) {
		pii u = V2.back();
		V2.pop_back();
		update(ch(u), Node());

		int st = i + 1, en = u.second;

		vector <pii> Vu2;
		while (st <= en) {
			pii u2 = pii(st, R[st] - 1);
			update(ch(u2), val[ch(u2)]);
			Vu2.push_back(u2);
			st = R[st];
		}
		reverse(all(Vu2));
		for (auto it : Vu2) V2.emplace_back(it);

		ans[(mnp + i) % N] = indt[1].s2 + in2[i];

		while (!V1.empty()) {
			int t = V1.back().first;
			if (in2[t] < in2[i]) break;

			update(ch(V1.back()), Node());
			V1.pop_back();
		}

		st = 1;
		if (!V1.empty()) st = V1.back().first + 1;
		V1.emplace_back(i, st);
		update(ch(V1.back()), val[ch(V1.back())]);
	}
	if (N % 2 == 1) {
		for (i = 0; i < N; i++) ans[i] += in[mnp];
	}
	
	int st = 1, en = N - 1;
	ans[mnp] = in[mnp];
	for(i = 1; i < N; i++) {
		if (in2[st] > in2[en]) {
			if (i % 2 == 0) ans[mnp] += in2[st];
			st++;
		}
		else {
			if (i % 2 == 0) ans[mnp] += in2[en];
			en--;
		}
	}
	for (i = 0; i < N; i++) printf("%lld\n", ans[i]);
	return 0;
}

Compilation message (stderr)

cake.cpp:23:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)  
 ^
cake.cpp:24:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:336777216")  
 ^
cake.cpp: In function 'int main()':
cake.cpp:163:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < Vx.size(); i++) {
                ^
cake.cpp:113:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
cake.cpp:114:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 0; i < N; i++) scanf("%d", &in[i]);
                                             ^

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