Submission #61250

#	Time	Username	Problem	Language	Result	Execution time	Memory
61250		Diuven	즐거운 사진 수집 (JOI13_collecting)	C++11	0 / 100	2361 ms	51000 KiB

collecting

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9;

int k, n, q;

struct st{
    uint8_t tree[1<<21];
    bool Arr[(1<<20)+1];
    int cnt[22];
    int len[22];
    void init(){
        cnt[k]=1;
        for(int i=k; i>=0; i--) len[i]=len[i+1]+cnt[i]*(1<<i);
    }
    ll upt(int v, int s, int e, int pos, int X[], int d=k){
        if(pos<s || e<pos) return 0LL;
        if(s==e){
            Arr[pos]=!Arr[pos];
            tree[v]=Arr[pos];
            return 0LL;
        }
        ll res=0;
        if(tree[v]!=3){
            res+=X[d]/(1<<d) * 4;
            cnt[d]--; cnt[d-1]+=2;
            tree[v]=3;
        }
        res+=upt(v*2,s,(s+e)/2,pos,X,d-1);
        res+=upt(v*2+1,(s+e)/2+1,e,pos,X,d-1);
        if(tree[v*2]==tree[v*2+1] && tree[v*2]!=3){
            res-=X[d]/(1<<d) * 4;
            cnt[d]++; cnt[d-1]--;
            tree[v]=tree[v*2];
        }
        return res;
    }
    ll upt(int pos, int S[]){
        ll ans=upt(1,1,n,pos,S);
        for(int i=k; i>=0; i--) len[i]=len[i+1]+(1<<i)*cnt[i];
        return ans;
    }
} X, Y;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>k>>q; n=(1<<k);
    X.init(); Y.init();
    ll ans=1;
    for(int i=1; i<=q; i++){
        int t, x; cin>>t>>x;
        st &A=(t==0 ? X : Y), &B=(t==1 ? X : Y);
        ans+=A.upt(x, B.len);
        cout<<ans<<'\n';
    }
    return 0;
}

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