oj.uz

Submission #49181

# Submission time Handle Problem Language Result Execution time Memory
49181 2018-05-23T07:21:22 Z ami Dojave (COCI17_dojave) C++14
14 / 140
 329 ms 38280 KB 
#include <bits/stdc++.h>
#define sz(c)      int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
#define bin(x) bitset<4>(x)
using namespace std;
using i64 = long long;

int const MAXN=1<<21;
int n;
int a[MAXN];
int to[MAXN];

int len_[MAXN];
i64 cnt_[MAXN][2];
auto len=len_+1;
auto cnt=cnt_+1;

i64 solve(int l,int r) {
  if (l==r) return 0;
  int m=(l+r)/2;
  i64 res=solve(l,m)+solve(m+1,r);
  int lo=m+1,hi=m;
  int i=m+1,j=m;
  while (l<=lo && hi<=r) {
    if (lo<i) {
      i-=1;
      lo=min(lo,to[a[i]]);
      hi=max(hi,to[a[i]]);
      continue;
    } else if (j<hi) {
      j+=1;
      lo=min(lo,to[a[j]]);
      hi=max(hi,to[a[j]]);
    } else {
      int curLen=j-i+1;

      rep(modL,0,2) rep(modR,0,2) {
        int mod=(modL+modR+curLen/2)%2;
        if (mod==0) {
          i64 cntL=(l<=i-1 ? cnt[i-1][modL] : 0) + (curLen>0 && modL==0 ? 1 : 0);
          i64 cntR=(j+1<=r ? cnt[j+1][modR] : 0) + (curLen>0 && modR==0 ? 1 : 0);
          res+=cntL*cntR;
        }
      }

      int lenL=(l<=i-1 ? len[i-1] : 0);
      int lenR=(j+1<=r ? len[j+1] : 0);
      lo-=lenL;
      hi+=lenR;

      assert(l<=lo && hi<=r);

      len[lo]=len[hi]=hi-lo+1;

      i64 addLo[2]={0,0};
      i64 addHi[2]={0,0};
      if (curLen+lenL>0) rep(modL,0,2) {
        int mod=(lenR/2+curLen/2+modL)%2;
        addHi[mod]+=cnt[lo][modL];
        if (curLen>0 && modL==0) {
          addHi[mod]+=1;
        }
      }
      if (curLen+lenR>0) rep(modR,0,2) {
        int mod=(lenL/2+curLen/2+modR)%2;
        addLo[mod]+=cnt[hi][modR];
        if (curLen>0 && modR==0) {
          addLo[mod]+=1;
        }
      }

      rep(mod,0,2) {
        cnt[lo][mod]+=addLo[mod];
        cnt[hi][mod]+=addHi[mod];
      }

      lo-=1;
      hi+=1;
    }
  }
  return res;
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout<<fixed<<setprecision(10);

  // freopen("02", "r", stdin);

  cin>>n;
  rep(i,0,1<<n) cin>>a[i];

  if (n==1) {
    cout<<2<<endl;
    return 0;
  }

  i64 N=1<<n;
  rep(i,0,1<<n) to[N-1-a[i]]=i;

  cout<<N*(N+1)/2-solve(0,(1<<n)-1)<<endl;

  return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 428 KB Output is correct
2 Incorrect 2 ms 460 KB Output isn't correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 796 KB Output is correct
2 Incorrect 4 ms 856 KB Output isn't correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 996 KB Output is correct
2 Incorrect 7 ms 996 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2404 KB Output is correct
2 Correct 18 ms 2404 KB Output is correct
3 Incorrect 31 ms 4280 KB Output isn't correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4280 KB Output is correct
2 Correct 27 ms 4280 KB Output is correct
3 Incorrect 73 ms 7800 KB Output isn't correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7812 KB Output is correct
2 Correct 68 ms 7984 KB Output is correct
3 Incorrect 87 ms 9584 KB Output isn't correct

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 31144 KB Output is correct
2 Incorrect 249 ms 31144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 31172 KB Output is correct
2 Correct 178 ms 31172 KB Output is correct
3 Incorrect 292 ms 38280 KB Output isn't correct
4 Halted 0 ms 0 KB -