Submission #782579

#	Time	Username	Problem	Language	Result	Execution time	Memory
782579		qwerasdfzxcl	케이크 (JOI13_cake)	C++17	100 / 100	283 ms	85600 KiB

cake

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
map<int, ll> mp[300300];
int n, a[300300];
ll sumE[600600], sumO[600600];

struct Seg{
	int tree[2002000];

	void init(int i, int l, int r){
		if (l==r){
			tree[i] = a[l];
			return;
		}

		int m = (l+r)>>1;
		init(i<<1, l, m); init(i<<1|1, m+1, r);
		tree[i] = min(tree[i<<1], tree[i<<1|1]);
	}

	int prefix(int i, int l, int r, int s, int x){
		if (r<s) return -1;
		if (tree[i] > x) return -1;
		if (l==r) return l;

		int m = (l+r)>>1;
		int ret = prefix(i<<1, l, m, s, x);
		if (ret!=-1) return ret;
		return prefix(i<<1|1, m+1, r, s, x);
	}

	int suffix(int i, int l, int r, int e, int x){
		// printf("   suffix %d %d %d %d %d / = %d\n", i, l, r, e, x, tree[i]);
		if (e<l) return -1;
		if (tree[i] > x) return -1;
		if (l==r) return l;

		int m = (l+r)>>1;
		int ret = suffix(i<<1|1, m+1, r, e, x);
		if (ret!=-1) return ret;
		return suffix(i<<1, l, m, e, x);
	}
}tree;

inline int dist(int s, int e){
	return (n+e-s) % n;
}

pair<int, int> getL(int l, int r, int typ){
	// naive
	// while(a[l] > a[r]){
	// 	l++;
	// 	typ ^= 1;
	// 	if (l>=n) l = 0;
	// }

	// return {l, typ};

	int ret = -1;
	if (l <= r){
		ret = tree.prefix(1, 0, n-1, l, a[r]);
	} 

	else{
		ret = tree.prefix(1, 0, n-1, l, a[r]);
		if (ret==-1) ret = tree.prefix(1, 0, n-1, 0, a[r]);
	}
	
	assert(ret!=-1);
	typ ^= dist(l, ret) % 2;
	return {ret, typ};
}

pair<int, int> getR(int l, int r, int typ){
	// naive
	// while(a[l] < a[r]){
	// 	r--;
	// 	typ ^= 1;
	// 	if (r<0) r = n-1;
	// }

	// return {r, typ};

	int ret = -1;
	if (l <= r){
		ret = tree.suffix(1, 0, n-1, r, a[l]);
	} 

	else{
		ret = tree.suffix(1, 0, n-1, r, a[l]);
		if (ret==-1) ret = tree.suffix(1, 0, n-1, n-1, a[l]);
	}

	assert(ret!=-1);
	typ ^= dist(ret, r) % 2;

	return {ret, typ};
}

ll sumL(int l, int r, int typ){
	// naive
	// ll ret = 0;
	// for (int i=l;;i=(i+1)%n){
	// 	if (typ) ret += a[i];
	// 	typ ^= 1;

	// 	if (i==r) break;
	// }

	// return ret;

	if (r<l) r += n;
	if ((l%2==0 && typ==1) || (l%2==1 && typ==0)) return sumE[r] - ((l==0)?0:sumE[l-1]);
	return sumO[r] - ((l==0)?0:sumO[l-1]);
}

ll sumR(int r, int l, int typ){
	// naive
	// ll ret = 0;
	// for (int i=r;;i=(n+i-1)%n){
	// 	if (typ) ret += a[i];
	// 	typ ^= 1;

	// 	if (i==l) break;
	// }

	// // printf(" ok %lld\n", ret);

	// return ret;

	if (r<l) r += n;
	if ((r%2==0 && typ==1) || (r%2==1 && typ==0)) return sumE[r] - ((l==0)?0:sumE[l-1]);
	return sumO[r] - ((l==0)?0:sumO[l-1]);
}

ll dfs(int l, int r, int typ){
	// printf(" call %d %d %d\n", l, r, typ);
	if (l==r) return (typ)?a[l]:0;
	if (mp[l].find(r)!=mp[l].end()) return mp[l][r];
	ll &ret = mp[l][r];

	if (a[l] > a[r]){
		auto [nl, nt] = getL(l, r, typ);
		// printf("  ok add %lld\n", sumL(l, (n+nl-1)%n, typ));
		return ret = sumL(l, (n+nl-1)%n, typ) + dfs(nl, r, nt);
	}

	auto [nr, nt] = getR(l, r, typ);
	// printf("  ok add %lld\n", sumR(r, (n+nr+1)%n, typ));
	return ret = sumR(r, (n+nr+1)%n, typ) + dfs(l, nr, nt);
}

int main(){
	scanf("%d", &n);
	for (int i=0;i<n;i++) scanf("%d", a+i);

	for (int i=0;i<n*2;i++){
		ll val = (i<n)?a[i]:a[i-n];

		if (i==0) sumE[i] = val;
		else if (i%2==0) sumE[i] = sumE[i-1] + val;
		else sumE[i] = sumE[i-1];

		if (i==0) sumO[i] = 0;
		else if (i%2==1) sumO[i] = sumO[i-1] + val;
		else sumO[i] = sumO[i-1];
	}

	tree.init(1, 0, n-1);

	for (int i=0;i<n;i++){
		int l = (n+i+1) % n, r = (n+i-1) % n;
		printf("%lld\n", a[i] + dfs(l, r, 0));
	}
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:156:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
cake.cpp:157:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |  for (int i=0;i<n;i++) scanf("%d", a+i);
      |                        ~~~~~^~~~~~~~~~~

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