Submission #40125

#	Time	Username	Problem	Language	Result	Execution time	Memory
40125		szawinis	Dojave (COCI17_dojave)	C++14	140 / 140	684 ms	52196 KiB

dojave

#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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14