Submission #49214

#	Time	Username	Problem	Language	Result	Execution time	Memory
49214		ami	Dojave (COCI17_dojave)	C++14	140 / 140	563 ms	53948 KiB

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;

template<typename T, typename Op>
struct segment_tree {
  int n;
  Op op;
  T identity;
  vector<T> f;
  explicit segment_tree(int n_, Op op_=Op(), T identity_=T())
    :n(n_), op(op_), identity(identity_), f(vector<T>(2*n, identity)) {}
  T& operator[](int i) {
    return f[i+n];
  }
  void build() {
    per(i,1,n) { f[i]=op(f[2*i],f[2*i+1]); }
  }
  void update(int i) {
    i+=n;
    for (i/=2; i>0; i/=2) { f[i]=op(f[2*i],f[2*i+1]); }
  }
  void update(int i, const T &x) {
    f[i]=x;
    update(i);
  }
  T query(int l, int r) {
    T L=identity;
    T R=identity;
    l+=n;
    r+=n;
    while (l<=r) {
      if (l%2==1) { L=op(L,f[l]); }
      if (r%2==0) { R=op(f[r],R); }
      l=(l+1)/2;
      r=(r-1)/2;
    }
    return op(L,R);
  }
};

template<typename T, typename Op>
segment_tree<T, Op> make_segment_tree(int n, Op op, T identity) {
  return segment_tree<T, Op>(n, op, identity);
}

int const MAXN=1<<20;
int n,N;
int a[MAXN];
int pos[MAXN];
int l[MAXN];
int r[MAXN];
int f[MAXN];
i64 dp[MAXN][2];
auto minTree = make_segment_tree(MAXN, [](int A,int B){ return min(A,B); }, MAXN);
auto maxTree = make_segment_tree(MAXN, [](int A,int B){ return max(A,B); }, 0);

int main() {
  // freopen("02", "r", stdin);

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

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

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

  rep(i,0,N) pos[a[i]]=i;
  rep(i,0,N) {
    minTree[i]=l[i]=min(pos[a[i]],pos[N-a[i]-1]);
    maxTree[i]=r[i]=max(pos[a[i]],pos[N-a[i]-1]);
  }
  minTree.build();
  maxTree.build();

  i64 res=i64(N+1)*N/2;
  rep(i,0,N) if (i==r[i]) {
    f[i]=-1;
    int mn=minTree.query(l[i],i);
    if (mn==l[i]) {
      f[i]=mn;
    } else if (r[mn]<i) {
      f[i]=f[r[mn]];
    }
    if (f[i]!=-1 && i==maxTree.query(f[i],i)) {
      int len=i-f[i]+1;
      int mod=(len/2)%2;
      dp[i][mod]=1;
      if (f[i]>0) {
        dp[i][mod]+=dp[f[i]-1][0];
        dp[i][mod^1]+=dp[f[i]-1][1];
      }
    }
    res-=dp[i][0];
  }

  cout<<res<<endl;

  return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14