# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
132597 | 2019-07-19T08:06:26 Z | anayk | Dojave (COCI17_dojave) | C++14 | 6 ms | 504 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 | 380 KB | Output is correct |
2 | Runtime error | 5 ms | 376 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 5 ms | 376 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 6 ms | 504 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 5 ms | 476 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 5 ms | 504 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 6 ms | 468 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 6 ms | 476 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 5 ms | 248 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 5 ms | 376 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 5 ms | 376 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |