oj.uz

Submission #77516

# Submission time Handle Problem Language Result Execution time Memory
77516 2018-09-28T10:28:04 Z zubec 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 1516 ms 48224 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;
    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;
        --x;
        if (type == 0){
            upd(0, x);
        } else {
            upd(1, x);
        }
        //ll ans = ((1<<n)*(1<<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 3 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 580 KB Output is correct
4 Correct 2 ms 664 KB Output is correct
5 Correct 2 ms 664 KB Output is correct
6 Correct 2 ms 664 KB Output is correct
7 Correct 2 ms 664 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 664 KB Output is correct
2 Correct 3 ms 664 KB Output is correct
3 Correct 3 ms 664 KB Output is correct
4 Correct 3 ms 668 KB Output is correct
5 Correct 3 ms 696 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 4 ms 736 KB Output is correct
8 Correct 3 ms 748 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1445 ms 43780 KB Output is correct
2 Correct 1453 ms 47764 KB Output is correct
3 Correct 1240 ms 47764 KB Output is correct
4 Correct 1381 ms 48224 KB Output is correct
5 Correct 1379 ms 48224 KB Output is correct
6 Correct 1363 ms 48224 KB Output is correct
7 Correct 1516 ms 48224 KB Output is correct
8 Correct 1452 ms 48224 KB Output is correct
9 Correct 1173 ms 48224 KB Output is correct
10 Correct 1274 ms 48224 KB Output is correct
11 Correct 1417 ms 48224 KB Output is correct
12 Correct 1354 ms 48224 KB Output is correct
13 Correct 1233 ms 48224 KB Output is correct