Submission #216327

#	Time	Username	Problem	Language	Result	Execution time	Memory
216327		rkm0959	즐거운 사진 수집 (JOI13_collecting)	C++17	100 / 100	1646 ms	64208 KiB

collecting

#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long double ldb;
typedef long long int ll;
typedef unsigned long long int ull;
typedef complex<double> base;

ll tot, cc, n, q;
ll cntA[21], cntB[21];
bool ONA[(1<<20)+300], ONB[(1<<20)+300];
int lg[(1<<20)+300], treeA[(1<<22)+400], treeB[(1<<22)+400];

void update_A(int index, int s, int e, int loc, bool v)
{
    if(s>loc || e<loc) return;
    if(s==loc && e==loc)
    {
        treeA[index]=v;
        return;
    }
    int m=(s+e)>>1;
    if(treeA[index]==0 || treeA[index]==e-s+1) cntA[lg[e-s+1]]--;
    update_A(index<<1, s, m, loc, v);
    update_A(index<<1|1, m+1, e, loc, v);
    treeA[index]=treeA[index<<1]+treeA[index<<1|1];
    if(treeA[index]==0 || treeA[index]==e-s+1) cntA[lg[e-s+1]]++;
}

void update_B(int index, int s, int e, int loc, int v)
{
    if(s>loc || e<loc) return;
    if(s==loc && e==loc)
    {
        treeB[index]=v;
        return;
    }
    int m=(s+e)>>1;
    if(treeB[index]==0 || treeB[index]==e-s+1) cntB[lg[e-s+1]]--;
    update_B(index<<1, s, m, loc, v);
    update_B(index<<1|1, m+1, e, loc, v);
    treeB[index]=treeB[index<<1]+treeB[index<<1|1];
    if(treeB[index]==0 || treeB[index]==e-s+1) cntB[lg[e-s+1]]++;
}

int main(void)
{
    fio; cin>>n>>q; int i, whi, x;
    for(i=0 ; i<=n ; i++) cntA[i]=cntB[i]=(1<<(n-i));
    for(i=0 ; i<=n ; i++) lg[1<<i]=i;
    for(i=0 ; i<=n ; i++) tot+=cntA[i]*cntB[i];
    while(q--)
    {
        cin>>whi>>x; cc=0;
        if(whi==0) { ONA[x]^=1; update_A(1, 1, 1<<n, x, ONA[x]); }
        if(whi==1) { ONB[x]^=1; update_B(1, 1, 1<<n, x, ONB[x]); }
        for(i=1 ; i<=n ; i++) cc+=4LL*cntA[i]*cntB[i];
        cout<<tot-cc<<"\n";
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70