제출 #132325

#제출 시각아이디문제언어결과실행 시간메모리
132325anaykDojave (COCI17_dojave)C++14
84 / 140
4017 ms36244 KiB
#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; void add(int x) { min = std::min(x, min); max = std::max(x, max); } void solve(int l = 0, int r = n-1) { int m = (l+r)/2; int a = m; int b = m+1; min = a; max = b; add(other[seq[a]]); add(other[seq[b]]); while(true) { //std::cout << min << " " << max << " " << a << " " << b << std::endl; 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]]); } } if(l == r) return; solve(l, m); solve(m+1, r); } int main() { std::cin >> m; n = (1 << m); for(int i = 0; i < n; i++) { std::cin >> seq[i]; first[i] = MAXN; other[seq[i]^(n-1)] = i; } solve(); 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]; } std::cout << answer << std::endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...