Submission #40083

#	Time	Username	Problem	Language	Result	Execution time	Memory
40083		top34051	Dojave (COCI17_dojave)	C++14	140 / 140	845 ms	51172 KiB

dojave

#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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14