oj.uz

답안 #40125

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
40125 2018-01-27T15:32:41 Z szawinis Dojave (COCI17_dojave) C++14
140 / 140
 684 ms 52196 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 20;

int m, n, a[N], l[N], r[N], trace[N];
bool state[N];
long long ans, dp[N][2];

int tmn[2*N], tmx[2*N];
void update_mn(int i, int v) {
	for(tmn[i += N] = v; i > 1; i >>= 1) tmn[i >> 1] = min(tmn[i], tmn[i ^ 1]);
}
int query_mn(int l, int r) {
	++r;
	int res = N;
	for(l += N, r += N; l < r; l >>= 1, r >>= 1) {
		if(l & 1) res = min(tmn[l++], res);
		if(r & 1) res = min(tmn[--r], res);
	}
	return res;
}
void update_mx(int i, int v) {
	for(tmx[i += N] = v; i > 1; i >>= 1) tmx[i >> 1] = max(tmx[i], tmx[i ^ 1]);
}
int query_mx(int l, int r) {
	++r;
	int res = -N;
	for(l += N, r += N; l < r; l >>= 1, r >>= 1) {
		if(l & 1) res = max(tmx[l++], res);
		if(r & 1) res = max(tmx[--r], res);
	}
	return res;
}
int main() {
	scanf("%d", &m);
	if(m == 1) printf("2"), exit(0);
	n = 1 << m;
	fill(l, l+N, N);
	fill(r, r+N, -1);
	for(int i = 0; i < n; i++) {
		scanf("%d", a+i);
		a[i] = min(a[i] ^ n-1, a[i]);
		l[a[i]] = min(i, l[a[i]]);
		r[a[i]] = max(i, r[a[i]]);
	}
	for(int i = 0; i < n; i++) {
		update_mn(i, l[a[i]]);
		update_mx(i, r[a[i]]);
	}
	for(int i = 0; i < n; i++) {
		if(i != r[a[i]]) continue;
		trace[i] = -1;
		int j = query_mn(l[a[i]], i);
		if(j >= l[a[i]]) trace[i] = j;
		else trace[i] = trace[r[a[j]]];
		if(trace[i] != -1 && query_mx(trace[i], i) <= i) {
			int p = (i - trace[i] + 1) / 2 % 2;
			dp[i][p] = 1;
			if(trace[i] > 0) {
				dp[i][p] += dp[trace[i]-1][0];
				dp[i][p ^ 1] += dp[trace[i]-1][1];
			}
			ans += dp[i][0];
		}
	}
	printf("%lld", 1ll * n * (n+1) / 2 - ans);
}

Compilation message

dojave.cpp: In function 'int main()':
dojave.cpp:42:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   a[i] = min(a[i] ^ n-1, a[i]);
                      ^
dojave.cpp:35:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
                 ^
dojave.cpp:41:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a+i);
                   ^

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 52196 KB Output is correct
2 Correct 6 ms 52196 KB Output is correct
3 Correct 0 ms 52196 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 52196 KB Output is correct
2 Correct 0 ms 52196 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 52196 KB Output is correct
2 Correct 3 ms 52196 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 52196 KB Output is correct
2 Correct 3 ms 52196 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 52196 KB Output is correct
2 Correct 6 ms 52196 KB Output is correct
3 Correct 11 ms 52196 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 52196 KB Output is correct
2 Correct 15 ms 52196 KB Output is correct
3 Correct 41 ms 52196 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 52196 KB Output is correct
2 Correct 41 ms 52196 KB Output is correct
3 Correct 77 ms 52196 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 52196 KB Output is correct
2 Correct 79 ms 52196 KB Output is correct
3 Correct 64 ms 52196 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 684 ms 52196 KB Output is correct
2 Correct 560 ms 52196 KB Output is correct
3 Correct 269 ms 52196 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 654 ms 52196 KB Output is correct
2 Correct 299 ms 52196 KB Output is correct
3 Correct 241 ms 52196 KB Output is correct
4 Correct 570 ms 52196 KB Output is correct