oj.uz

Submission #49214

# Submission time Handle Problem Language Result Execution time Memory
49214 2018-05-23T23:08:09 Z ami Dojave (COCI17_dojave) C++14
140 / 140
 563 ms 53948 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)
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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16760 KB Output is correct
2 Correct 17 ms 16996 KB Output is correct
3 Correct 14 ms 16996 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17012 KB Output is correct
2 Correct 17 ms 17020 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 17148 KB Output is correct
2 Correct 18 ms 17180 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17384 KB Output is correct
2 Correct 18 ms 17384 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17416 KB Output is correct
2 Correct 19 ms 17656 KB Output is correct
3 Correct 21 ms 17656 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 18332 KB Output is correct
2 Correct 35 ms 18680 KB Output is correct
3 Correct 40 ms 21752 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 21752 KB Output is correct
2 Correct 56 ms 21752 KB Output is correct
3 Correct 64 ms 26336 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 26336 KB Output is correct
2 Correct 89 ms 26336 KB Output is correct
3 Correct 68 ms 26360 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 37532 KB Output is correct
2 Correct 327 ms 37752 KB Output is correct
3 Correct 174 ms 53940 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 53940 KB Output is correct
2 Correct 301 ms 53940 KB Output is correct
3 Correct 192 ms 53948 KB Output is correct
4 Correct 547 ms 53948 KB Output is correct