Submission #43195

#	Time	Username	Problem	Language	Result	Execution time	Memory
43195		smu201111192	즐거운 사진 수집 (JOI13_collecting)	C++14	100 / 100	2262 ms	60660 KiB

collecting

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = (1<<21);
const int dep = 22;
int n,q;
long long rtree[MAXN],ctree[MAXN];
long long rsum[MAXN],csum[MAXN];
void update(int node,int st,int ed,int pos,long long *tree,long long *sum,int dep){
    if(pos > ed || pos < st)return;
    if(st == ed){
        tree[node] ^= 1;
        return;
    }
    if(tree[node] == 0 || tree[node] == (1LL <<(n-dep))) sum[dep]--;
    update(node*2,st,(st+ed)/2,pos,tree,sum,dep+1);
    update(node*2+1,(st+ed)/2+1,ed,pos,tree,sum,dep+1);
    tree[node] = tree[node * 2] + tree[node * 2 +1];
    if(tree[node] == 0 || tree[node] == (1LL <<(n-dep))) sum[dep]++;
    return;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> q;
    for(int i = 0; i <= n; i++){
        rsum[i] = csum[i] = (1LL << i);
    }
    for(int i = 1; i <= q; i++){
        int type; int line;
        cin >> type >> line;
        if(type == 0) update(1,1,(1<<n),line,rtree,rsum,0);
        else update(1,1,(1<<n),line,ctree,csum,0);
        long long ret = 0;
        long long last = 0;
        for(int j = 0; j <= n; j++){
            long long a = 1<<j;
            long long b = 1<<j;
            ret += a * b;
            ret -= 4 * last;
            last = rsum[j] * csum[j];
        }
        cout<<ret<<"\n";
    }
    
    return 0;
}

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