Submission #49210

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49210	2018-05-23T19:37:22 Z	ami	Dojave (COCI17_dojave)	C++14	140 / 140	274 ms	29820 KB

dojave

#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)
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]]);
    } else if (j<hi) {
      j+=1;
      lo=min(lo,to[a[j]]);
      hi=max(hi,to[a[j]]);
    } else {
      int curLen=j-i+1;
      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);

      rep(modL,0,2) rep(modR,0,2) if ((curLen/2+modL+modR)%2==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;
        // if (cntL*cntR>0) {
        //   cerr<<l<<" "<<r<<endl<<lo<<" "<<hi<<" "<<i<<" "<<j<<endl;
        //   cerr<<modL<<" "<<modR<<endl;
        //   cerr<<cntL<<" "<<cntR<<endl;
        //   cerr<<cntL*cntR<<endl;
        //   cerr<<endl;
        // }
      }

      if (lo<=m && m<hi) {
        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;
          if (l<=i-1) { addHi[mod]+=cnt[i-1][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;
          if (j+1<=r) { addLo[mod]+=cnt[j+1][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() {
  // freopen("00", "r", stdin);

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

  cin>>n;
  int N=1<<n;
  rep(i,0,N) cin>>a[i];
  // rep(i,0,N) cerr<<setw(3)<<i;
  // cerr<<endl;
  // rep(i,0,N) cerr<<setw(3)<<a[i];
  // cerr<<endl;
  // rep(i,0,N) cerr<<setw(3)<<char(min(a[i],N-1-a[i])+'a');
  // cerr<<endl;
  // rep(i,0,N) cerr<<setw(3)<<(10<=i && i<=30?'+':' ');
  // cerr<<endl;

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

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

  // cerr<<solve(10,30)<<endl;
  // return 0;

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

  // int i=10; {
  // // rep(i,0,N) {
  //   rep(j,0,N) {
  //     if (i>=j) {
  //       cout<<setw(3)<<0;
  //       continue;
  //     }
  //     memset(len_,0,sizeof(len_));
  //     memset(cnt_,0,sizeof(cnt_));
  //     cout<<setw(3)<<solve(i,j);
  //   }
  //   cout<<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	4 ms	560 KB	Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	684 KB	Output is correct
2	Correct	4 ms	692 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	968 KB	Output is correct
2	Correct	4 ms	968 KB	Output is correct

Subtask #5
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	968 KB	Output is correct
2	Correct	6 ms	1164 KB	Output is correct
3	Correct	6 ms	1380 KB	Output is correct

Subtask #6
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	1388 KB	Output is correct
2	Correct	18 ms	2668 KB	Output is correct
3	Correct	26 ms	4600 KB	Output is correct

Subtask #7
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	4600 KB	Output is correct
2	Correct	25 ms	4600 KB	Output is correct
3	Correct	51 ms	8128 KB	Output is correct

Subtask #8
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	8128 KB	Output is correct
2	Correct	44 ms	8128 KB	Output is correct
3	Correct	51 ms	8128 KB	Output is correct

Subtask #9
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	274 ms	9296 KB	Output is correct
2	Correct	218 ms	9540 KB	Output is correct
3	Correct	241 ms	29808 KB	Output is correct

Subtask #10
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	228 ms	29808 KB	Output is correct
2	Correct	192 ms	29808 KB	Output is correct
3	Correct	197 ms	29820 KB	Output is correct
4	Correct	229 ms	29820 KB	Output is correct

Submission #49210

Compilation message