oj.uz

답안 #782579

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
782579 2023-07-14T06:00:29 Z qwerasdfzxcl 케이크 (JOI13_cake) C++17
100 / 100
 283 ms 85600 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15444 KB Output is correct
2 Correct 10 ms 15324 KB Output is correct
3 Correct 10 ms 15512 KB Output is correct
4 Correct 11 ms 15432 KB Output is correct
5 Correct 9 ms 15316 KB Output is correct
6 Correct 9 ms 15316 KB Output is correct
7 Correct 9 ms 15316 KB Output is correct
8 Correct 10 ms 15444 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 9 ms 14420 KB Output is correct

Subtask #2
90.0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 35152 KB Output is correct
2 Correct 66 ms 33956 KB Output is correct
3 Correct 76 ms 35532 KB Output is correct
4 Correct 170 ms 64988 KB Output is correct
5 Correct 145 ms 57688 KB Output is correct
6 Correct 221 ms 80352 KB Output is correct
7 Correct 283 ms 85600 KB Output is correct
8 Correct 215 ms 80024 KB Output is correct
9 Correct 240 ms 80240 KB Output is correct
10 Correct 274 ms 74056 KB Output is correct
11 Correct 212 ms 80620 KB Output is correct
12 Correct 208 ms 74832 KB Output is correct
13 Correct 176 ms 74928 KB Output is correct
14 Correct 238 ms 74104 KB Output is correct
15 Correct 205 ms 78152 KB Output is correct