# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
132600 | 2019-07-19T08:11:59 Z | anayk | Dojave (COCI17_dojave) | C++14 | 343 ms | 29304 KB |
#include <iostream> #define MAXN 2000000 int m, n; int first[MAXN]; int other[MAXN]; int seq[MAXN]; long long dp[2][MAXN]; int min, max; int a, b; void add(int x) { min = std::min(x, min); max = std::max(x, max); } void solve(int l, int r) { int m = (l+r)/2; a = m; b = m+1; min = a; max = b; add(other[seq[a]]); add(other[seq[b]]); while(true) { if(a > min) { if(a == l) break; a--; add(other[seq[a]]); } else if(b < max) { if(b == r) break; b++; add(other[seq[b]]); } else { first[a] = std::min(first[a], b); if(a == l) break; a--; add(other[seq[a]]); } } } int main() { scanf("%d", &m); n = (1 << m); if(m == 1) { printf("%d", 2); return 0; } for(int i = 0; i < n; i++) { scanf("%d", seq + i); first[i] = MAXN; other[seq[i]^(n-1)] = i; } int c = 2; while(c <= n) { for(int i = 0; i < n; i+=c) solve(i, i+c-1); c *= 2; } long long answer = n; answer *= (answer-1); answer /= 2; answer += (long long) n; dp[0][n] = dp[1][n] = 0; for(int i = n-1; i >= 0; i--) { dp[0][i] = dp[1][i] = 0; if(first[i] == MAXN) continue; int c = first[i]-i+1; if(c%4) { dp[1][i] = 1; dp[1][i] += dp[0][first[i]+1]; dp[0][i] += dp[1][first[i]+1]; } else { dp[0][i] = 1; dp[1][i] += dp[1][first[i]+1]; dp[0][i] += dp[0][first[i]+1]; } answer -= dp[0][i]; } printf("%lld", answer); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 504 KB | Output is correct |
2 | Correct | 3 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 508 KB | Output is correct |
2 | Correct | 3 ms | 508 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 760 KB | Output is correct |
2 | Correct | 5 ms | 760 KB | Output is correct |
3 | Correct | 5 ms | 760 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 2168 KB | Output is correct |
2 | Correct | 12 ms | 2168 KB | Output is correct |
3 | Correct | 31 ms | 3960 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 2168 KB | Output is correct |
2 | Correct | 24 ms | 3960 KB | Output is correct |
3 | Correct | 56 ms | 7528 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 67 ms | 7644 KB | Output is correct |
2 | Correct | 48 ms | 7576 KB | Output is correct |
3 | Correct | 56 ms | 7544 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 327 ms | 29152 KB | Output is correct |
2 | Correct | 287 ms | 29196 KB | Output is correct |
3 | Correct | 236 ms | 29180 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 343 ms | 29172 KB | Output is correct |
2 | Correct | 180 ms | 29048 KB | Output is correct |
3 | Correct | 216 ms | 29048 KB | Output is correct |
4 | Correct | 310 ms | 29304 KB | Output is correct |