oj.uz

Submission #77520

# Submission time Handle Problem Language Result Execution time Memory
77520 2018-09-28T10:30:59 Z zubec 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 1459 ms 44124 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){
        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);
        //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-1)/3+1 << "\n";
    }

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 532 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Correct 2 ms 592 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 608 KB Output is correct
2 Correct 3 ms 608 KB Output is correct
3 Correct 3 ms 624 KB Output is correct
4 Correct 3 ms 624 KB Output is correct
5 Correct 3 ms 644 KB Output is correct
6 Correct 3 ms 644 KB Output is correct
7 Correct 3 ms 644 KB Output is correct
8 Correct 3 ms 656 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1320 ms 43864 KB Output is correct
2 Correct 1459 ms 44024 KB Output is correct
3 Correct 1204 ms 44024 KB Output is correct
4 Correct 1456 ms 44124 KB Output is correct
5 Correct 1331 ms 44124 KB Output is correct
6 Correct 1225 ms 44124 KB Output is correct
7 Correct 1316 ms 44124 KB Output is correct
8 Correct 1335 ms 44124 KB Output is correct
9 Correct 1198 ms 44124 KB Output is correct
10 Correct 1366 ms 44124 KB Output is correct
11 Correct 1415 ms 44124 KB Output is correct
12 Correct 1418 ms 44124 KB Output is correct
13 Correct 1223 ms 44124 KB Output is correct