oj.uz

답안 #40083

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
40083 2018-01-26T14:49:17 Z top34051 Dojave (COCI17_dojave) C++14
140 / 140
 845 ms 51172 KB 
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int maxn = (1<<20) + 5;
const int inf = 1e9;
int n,sz;
int a[maxn], p[maxn];
pii tree[maxn*4];
int dp[maxn][2];
pii get(pii a,pii b) {
    return {min(a.X,b.X), max(a.Y,b.Y)};
}
void build(int pos,int l,int r) {
    if(l==r) {
        tree[pos] = {min(p[a[l]],p[(sz-1)^a[l]]), max(p[a[l]],p[(sz-1)^a[l]])};
        return ;
    }
    int mid = (l+r)/2;
    build(pos<<1,l,mid); build(pos<<1|1,mid+1,r);
    tree[pos] = get(tree[pos<<1],tree[pos<<1|1]);
}
void update(int pos,int l,int r,int x,pii val) {
    if(l>r || r<x || x<l) return ;
    if(l==r) {
        tree[pos] = get(tree[pos],val);
        return ;
    }
    int mid = (l+r)/2;
    update(pos<<1,l,mid,x,val); update(pos<<1|1,mid+1,r,x,val);
    tree[pos] = get(tree[pos<<1],tree[pos<<1|1]);
}
pii query(int pos,int l,int r,int x,int y) {
    if(l>r || r<x || y<l) return {inf,-inf};
    if(x<=l && r<=y) return tree[pos];
    int mid = (l+r)/2;
    return get(query(pos<<1,l,mid,x,y), query(pos<<1|1,mid+1,r,x,y));
}
int main() {
	int i,x,y;
	long long ans;
	scanf("%d",&n);
	if(n==1) return !printf("2");
	sz = (1<<n); ans = (long long)sz*(sz+1)/2;
	for(i=1;i<=sz;i++) scanf("%d",&a[i]), p[a[i]] = i;
	build(1,1,sz);
	for(i=1;i<=sz;i++) {
//        printf("i = %d : (%d, %d)\n",i,i,pos[(sz-1)^a[i]]);
        if(p[(sz-1)^a[i]]>i) continue;
        auto temp = query(1,1,sz,p[(sz-1)^a[i]],i);
        update(1,1,sz,i,temp);
        x = temp.X; y = temp.Y;
        if(y>i) continue;
        if(((i-x+1)/2)%2==0) {
            dp[i][0] = dp[x-1][0] + 1;
            dp[i][1] = dp[x-1][1];
        }
        else {
            dp[i][0] = dp[x-1][1];
            dp[i][1] = dp[x-1][0] + 1;
        }
        ans -= dp[i][0];
	}
	printf("%lld",ans);
}

Compilation message

dojave.cpp: In function 'int main()':
dojave.cpp:43:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
dojave.cpp:46:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=sz;i++) scanf("%d",&a[i]), p[a[i]] = i;
                                                   ^

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 51172 KB Output is correct
2 Correct 0 ms 51172 KB Output is correct
3 Correct 0 ms 51172 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 51172 KB Output is correct
2 Correct 0 ms 51172 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 51172 KB Output is correct
2 Correct 2 ms 51172 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 51172 KB Output is correct
2 Correct 4 ms 51172 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 51172 KB Output is correct
2 Correct 6 ms 51172 KB Output is correct
3 Correct 6 ms 51172 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 51172 KB Output is correct
2 Correct 25 ms 51172 KB Output is correct
3 Correct 63 ms 51172 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 51172 KB Output is correct
2 Correct 60 ms 51172 KB Output is correct
3 Correct 119 ms 51172 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 51172 KB Output is correct
2 Correct 130 ms 51172 KB Output is correct
3 Correct 119 ms 51172 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 845 ms 51172 KB Output is correct
2 Correct 719 ms 51172 KB Output is correct
3 Correct 409 ms 51172 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 828 ms 51172 KB Output is correct
2 Correct 515 ms 51172 KB Output is correct
3 Correct 439 ms 51172 KB Output is correct
4 Correct 799 ms 51172 KB Output is correct