제출 #49201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49201		ami	Dojave (COCI17_dojave)	C++14	0 / 140	4098 ms	262144 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 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: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14