oj.uz

Submission #12974

# Submission time Handle Problem Language Result Execution time Memory
12974 2015-01-22T17:37:20 Z dohyun0324 즐거운 사진 수집 (JOI13_collecting) C++
100 / 100
 3844 ms 59680 KB 
#include<stdio.h>
typedef long long ll;
int gap,r,t,n,q,cnt[2][21],pos[5000010],sw,tree[2][5000010];
ll dap[21],arr[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]==arr[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]==arr[pos[k]]){
        if(pos[k]==1) cnt[p][pos[k*2]]--;
        cnt[p][pos[k*2]]--;
        sw=1;
        r=k;
    }
}
void pro()
{
    int i;
    ll sum=0,ans=0;
    for(i=n;i>=0;i--){
        sum+=arr[i]*ll(cnt[0][i]);
        dap[i]=sum/arr[i]*ll(cnt[1][i]);
    }
    sum=0;
    for(i=n;i>=0;i--){
        dap[i]+=sum/arr[i]*ll(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("%lld\n",ans);
}
int main()
{
    int i,j,x,p,w=1,c=0;
    scanf("%d %d",&n,&q); t=1<<n;
    for(i=0;i<=20;i++) arr[i]=1<<i;
    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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3788 ms 59680 KB Output is correct
2 Correct 3844 ms 59680 KB Output is correct
3 Correct 3332 ms 59680 KB Output is correct
4 Correct 3792 ms 59680 KB Output is correct
5 Correct 3700 ms 59680 KB Output is correct
6 Correct 3648 ms 59680 KB Output is correct
7 Correct 3784 ms 59680 KB Output is correct
8 Correct 3692 ms 59680 KB Output is correct
9 Correct 3168 ms 59680 KB Output is correct
10 Correct 3316 ms 59680 KB Output is correct
11 Correct 3608 ms 59680 KB Output is correct
12 Correct 3628 ms 59680 KB Output is correct
13 Correct 3344 ms 59680 KB Output is correct