oj.uz

답안 #77521

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
77521 2018-09-28T10:31:20 Z zubec 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 1526 ms 45036 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)-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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 420 KB Output is correct
4 Correct 2 ms 424 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 3 ms 636 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 636 KB Output is correct
2 Correct 4 ms 644 KB Output is correct
3 Correct 4 ms 668 KB Output is correct
4 Correct 3 ms 696 KB Output is correct
5 Correct 3 ms 696 KB Output is correct
6 Correct 3 ms 696 KB Output is correct
7 Correct 3 ms 700 KB Output is correct
8 Correct 3 ms 708 KB Output is correct

Subtask #3
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1338 ms 43896 KB Output is correct
2 Correct 1387 ms 44456 KB Output is correct
3 Correct 1228 ms 44456 KB Output is correct
4 Correct 1526 ms 45036 KB Output is correct
5 Correct 1363 ms 45036 KB Output is correct
6 Correct 1323 ms 45036 KB Output is correct
7 Correct 1339 ms 45036 KB Output is correct
8 Correct 1279 ms 45036 KB Output is correct
9 Correct 1126 ms 45036 KB Output is correct
10 Correct 1291 ms 45036 KB Output is correct
11 Correct 1343 ms 45036 KB Output is correct
12 Correct 1322 ms 45036 KB Output is correct
13 Correct 1157 ms 45036 KB Output is correct