oj.uz

Submission #49079

# Submission time Handle Problem Language Result Execution time Memory
49079 2018-05-22T00:01:38 Z ami Dojave (COCI17_dojave) C++14
0 / 140
 319 ms 26064 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;

int const MAXN=1<<20;
int n;
int a[MAXN];
int to[MAXN];

i64 solve(int l,int r) {
  if (r-l<=1) return 0;
  int m=(l+r)/2;
  i64 res=solve(l,m)+solve(m+1,r);
  int i=m,j=m+1;
  int lo=to[a[i]];
  int hi=to[a[j]];
  if (lo>hi) swap(lo,hi);
  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 {
      break;
    }
  }
  if (i==lo && j==hi) res+=1;
  return res;
}

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];

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

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

  return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 2284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 5572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 319 ms 18728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 262 ms 26064 KB Output isn't correct
2 Halted 0 ms 0 KB -