oj.uz

Submission #49200

# Submission time Handle Problem Language Result Execution time Memory
49200 2018-05-23T14:49:58 Z ami Dojave (COCI17_dojave) C++14
70 / 140
 4000 ms 262144 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 Node, int N>
struct segment_tree {
  Node tr[2*N];
  Node& operator[](int i) {
    return tr[i+N];
  }
  void build() {
    per(i,1,N) { tr[i]=merge_nodes(tr[2*i],tr[2*i+1]); }
  }
  void update(int i) {
    i+=N;
    for (i/=2; i>0; i/=2) { tr[i]=merge_nodes(tr[2*i],tr[2*i+1]); }
  }
  void update(int i, const Node &x) {
    tr[i]=x;
    update(i);
  }
  Node query(int l, int r) {
    Node L,R;
    l+=N;
    r+=N;
    while (l<=r) {
      if (l%2==1) { L=merge_nodes(L,tr[l]); }
      if (r%2==0) { R=merge_nodes(tr[r],R); }
      l=(l+1)/2;
      r=(r-1)/2;
    }
    return merge_nodes(L,R);
  }
};

struct node {
  int min,max;
  node():min(-1),max(-1) {}
  node(int x):min(x),max(x) {}
  node(int mn,int mx):min(mn),max(mx) {}
};

node merge_nodes(const node &a, const node &b) {
  if (a.min==-1) return b;
  if (b.min==-1) return a;
  return node(min(a.min,b.min),max(a.max,b.max));
}

int const MAXN=1<<21;
int n,N;
int a[MAXN];
int p[MAXN];
int to[MAXN];
vector<int> pos[MAXN][4];
segment_tree<node,1<<20> tr;

bool check(int l, int r) {
  node v=tr.query(l,r-1);
  return l<=v.min && v.max<r;
}

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

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

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

  N=1<<n;

  rep(i,0,1<<n) to[N-a[i]-1]=i;
  rep(i,0,1<<n) tr[i]=node(to[a[i]]);
  tr.build();

  int ps=0;
  pos[0][0].push_back(0);
  rep(i,0,1<<n) {
    ps=ps^a[i];
    pos[ps][(i+1)%4].push_back(i+1);
  }

  i64 res=i64(N+1)*N/2;
  rep(i,0,1<<n) {
    rep(ml,0,4) rep(mr,0,4) if ((mr-ml+4)%4==0) {
      auto &L=pos[i][ml];
      auto &R=pos[i][mr];
      int k=0;
      for (int l:L) {
        while (k<sz(R) && R[k]<=l) k+=1;
        rep(r,k,sz(R)) if (check(l,R[r])) res-=1;
      }
    }
  }
  cout<<res<<endl;

  return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 213752 KB Output is correct
2 Correct 180 ms 213860 KB Output is correct
3 Correct 290 ms 213860 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 213896 KB Output is correct
2 Correct 183 ms 213896 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 214020 KB Output is correct
2 Correct 197 ms 214020 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 214264 KB Output is correct
2 Correct 186 ms 214264 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 214532 KB Output is correct
2 Correct 1341 ms 214532 KB Output is correct
3 Correct 1916 ms 214552 KB Output is correct

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 216304 KB Output is correct
2 Execution timed out 4030 ms 216304 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 216332 KB Output is correct
2 Execution timed out 4027 ms 217620 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 223516 KB Output is correct
2 Execution timed out 4059 ms 223516 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4104 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -