Submission #24933

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
24933	2017-06-17T09:43:33 Z	dotorya	케이크 (JOI13_cake)	C++14	100 / 100	923 ms	93584 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	77300 KB	Output is correct
2	Correct	13 ms	77320 KB	Output is correct
3	Correct	36 ms	77308 KB	Output is correct
4	Correct	23 ms	77300 KB	Output is correct
5	Correct	19 ms	77300 KB	Output is correct
6	Correct	13 ms	77300 KB	Output is correct
7	Correct	6 ms	77300 KB	Output is correct
8	Correct	29 ms	77308 KB	Output is correct
9	Correct	6 ms	77028 KB	Output is correct
10	Correct	13 ms	77028 KB	Output is correct
11	Correct	13 ms	77028 KB	Output is correct

Subtask #2

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	213 ms	80216 KB	Output is correct
2	Correct	199 ms	80216 KB	Output is correct
3	Correct	199 ms	80248 KB	Output is correct
4	Correct	716 ms	83256 KB	Output is correct
5	Correct	563 ms	83260 KB	Output is correct
6	Correct	716 ms	89400 KB	Output is correct
7	Correct	569 ms	91708 KB	Output is correct
8	Correct	846 ms	89432 KB	Output is correct
9	Correct	923 ms	89400 KB	Output is correct
10	Correct	569 ms	93496 KB	Output is correct
11	Correct	643 ms	89980 KB	Output is correct
12	Correct	549 ms	90684 KB	Output is correct
13	Correct	543 ms	93500 KB	Output is correct
14	Correct	486 ms	93584 KB	Output is correct
15	Correct	619 ms	90428 KB	Output is correct