제출 #77521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
77521		zubec	즐거운 사진 수집 (JOI13_collecting)	C++14	100 / 100	1526 ms	45036 KiB

collecting

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

int cnt[2][25], t[2][(1<<21) + 100], n;

inline void upd(int id, int pos){
    int v = ((1<<n)+pos)-1;
    int sz = 1;
    int deep = n;
    t[id][v] ^= 1;
    v>>=1;
    sz += sz;
    --deep;
    while(v){
        if (t[id][v] % sz == 0){
            --cnt[id][deep];
        }
        t[id][v] = t[id][v+v] + t[id][v+v+1];
        if (t[id][v] % sz == 0)
            ++cnt[id][deep];
        v>>=1;
        sz += sz;
        --deep;
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tt;
    cin >> n >> tt;
    for (int i = 0; i <= n; i++)
        cnt[0][i] = cnt[1][i] = (1<<i);
    while(tt--){
        int type, x;
        cin >> type >> x;
        if (type == 0){
            upd(0, x);
        } else {
            upd(1, x);
        }
        //ll ans = ((1ll<<n)*(1ll<<n)-1)/3;
        ll ans = ((1ll<<n)*(1ll<<n)-1)/3;
        //cout << "kek " << ans << ' ';
        for (int i = 0; i < n; i++){
            ans -= (ll)cnt[0][i]*(ll)cnt[1][i];
            //cout << i << ' ' << cnt[0][i] << ' ' << cnt[1][i] << endl;
        }
        cout << 4*ans+1 << "\n";
    }

}

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