Submission #633674

#	Time	Username	Problem	Language	Result	Execution time	Memory
633674		Fake4Fun	즐거운 사진 수집 (JOI13_collecting)	C++14	100 / 100	897 ms	61840 KiB

collecting

#include<iostream>
#define FBIT(x) ((1<<x)-1)
using namespace std;
const int N=1<<20;
int n,q;
int al[2][22],IT[2][N<<1];
void update(int id,int p){
    short dif=(!IT[id][p]?1:-1), layer=0;
    IT[id][p]^=1;
    while(p!=1){
        p>>=1, ++layer;
        bool o=!(IT[id][p]&FBIT(layer));
        al[id][layer]-=o;
        IT[id][p]+=dif;
        o=!(IT[id][p]&FBIT(layer));
        al[id][layer]+=o;
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) al[0][i]=al[1][i]=1<<(n-i);
    int id,x;
    long long ans;
    while(q--){
        cin>>id>>x;
        update(id,(1<<n)+x-1);
        ans=0;
        for(int i=n;i>=0;i--)
            ans+=(1ll<<(2*(n-i)))-(4ll*al[0][i+1]*al[1][i+1]);
        cout<<ans<<'\n';
    }
    return 0;
}

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