oj.uz

답안 #12973

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12973 2015-01-22T17:18:56 Z dohyun0324 즐거운 사진 수집 (JOI13_collecting) C++
30 / 100
 2920 ms 59680 KB 
#include<stdio.h>
int gap,r,t,n,q,cnt[2][21],pos[5000010],sw,dap[21],tree[2][5000010],hap[21];
void update(int p,int s,int x,int y,int k)
{
    if(x==y){
        if(tree[p][k]==0) tree[p][k]=1, gap=1;
        else tree[p][k]=0, gap=-1;
        return;
    }
    if(tree[p][k]==0 || tree[p][k]==1<<pos[k]) cnt[p][pos[k]]--, cnt[p][pos[k*2]]+=2;
    if(s<=(x+y)/2) update(p,s,x,(x+y)/2,k*2);
    else update(p,s,(x+y)/2+1,y,k*2+1);
    tree[p][k]=tree[p][k]+gap;
    if(tree[p][k]==0 || tree[p][k]==1<<pos[k]){
        if(pos[k]==1) cnt[p][pos[k*2]]--;
        cnt[p][pos[k*2]]--;
        sw=1;
        r=k;
    }
}
void pro()
{
    int i,sum=0,ans=0;
    for(i=n;i>=0;i--){
        sum+=(1<<i)*cnt[0][i];
        dap[i]=sum/(1<<i)*cnt[1][i];
    }
    sum=0;
    for(i=n;i>=0;i--){
        dap[i]+=sum/(1<<i)*cnt[0][i];
        sum+=(1<<i)*cnt[1][i];
    }
    for(i=0;i<=n;i++) ans+=dap[i];
    for(i=0;i<=n;i++){
        dap[i]/=4;
        ans+=dap[i];
        dap[i+1]+=dap[i];
    }
    printf("%d\n",ans);
}
int main()
{
    int i,j,x,p,w=1,c=0;
    scanf("%d %d",&n,&q); t=1<<n;
    for(i=1;i<=t*2;i++){
        c++;
        for(j=i;j<=i+w-1;j++) pos[j]=n-c+1;
        i=j-1; w*=2;
    }
    cnt[0][pos[1]]=cnt[1][pos[1]]=1;
    for(i=1;i<=q;i++){
        scanf("%d %d",&p,&x); sw=0;
        r=0; update(p,x,1,t,1);
        if(r) cnt[p][pos[r]]++;
        pro();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 59680 KB Output is correct
2 Correct 0 ms 59680 KB Output is correct
3 Correct 0 ms 59680 KB Output is correct
4 Correct 0 ms 59680 KB Output is correct
5 Correct 0 ms 59680 KB Output is correct
6 Correct 0 ms 59680 KB Output is correct
7 Correct 0 ms 59680 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 59680 KB Output is correct
2 Correct 0 ms 59680 KB Output is correct
3 Correct 0 ms 59680 KB Output is correct
4 Correct 0 ms 59680 KB Output is correct
5 Correct 0 ms 59680 KB Output is correct
6 Correct 0 ms 59680 KB Output is correct
7 Correct 0 ms 59680 KB Output is correct
8 Correct 0 ms 59680 KB Output is correct

Subtask #3
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2920 ms 59680 KB Output isn't correct
2 Halted 0 ms 0 KB -