oj.uz

Submission #77518

# Submission time Handle Problem Language Result Execution time Memory
77518 2018-09-28T10:30:11 Z zubec 즐거운 사진 수집 (JOI13_collecting) C++14
0 / 100
 1453 ms 43756 KB 
#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 > 1){
        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);
        --ans;
        //cout << "kek " << ans << ' ';
        for (int i = 0; i < n; i++){
            ans -= (ll)cnt[0][i]*(ll)cnt[1][i]*3;
            //cout << i << ' ' << cnt[0][i] << ' ' << cnt[1][i] << endl;
        }
        cout << 4*ans/3+1 << "\n";
    }

}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 1453 ms 43756 KB Output isn't correct
2 Halted 0 ms 0 KB -