oj.uz

Submission #821780

# Submission time Handle Problem Language Result Execution time Memory
821780 2023-08-11T16:22:36 Z nonono 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 3194 ms 111120 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mxN = 20;

int n, q;
int f[mxN + 5];

struct seg_tree {
    vector<int> ST, cnt;
    
    void init(int n) {
        ST.resize((1 << n) * 4);
        cnt.resize(n + 5);
        
        for(int i = 1; i <= (1 << n) * 4; i ++) ST[i] = 0;
        for(int i = 0; i <= n; i ++) cnt[i] = 0;
        
        cnt[n] ++ ;
    }
    
    void update(int id, int l, int r, int x) {
        int k = log2(r - l + 1);
        if(!ST[id] || ST[id] == r - l + 1) {
            if(cnt[k]) {
                cnt[k] -- ;
                if(k > 0) cnt[k - 1] += 2;
            }
        }
        
        if(l == r) {
            ST[id] = !ST[id];
            return ;
        }
        
        int mid = (l + r) / 2;
        if(x <= mid) update(id * 2, l, mid, x); 
        else 
            update(id * 2 + 1, mid + 1, r, x);
        
        ST[id] = ST[id * 2] + ST[id * 2 + 1];
        if(!ST[id] || ST[id] == r - l + 1) {
            cnt[k] ++ ;
            cnt[k - 1] -= 2;
        }
    }
};

seg_tree a, b;

signed main() {
 
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n >> q;
    
    f[0] = 1;
    for(int i = 1; i <= n; i ++) {
        f[i] = 4 * f[i - 1] + 1;
    }
    
    a.init(n);
    b.init(n);
    
    while(q --) {
        int t, x;
        cin >> t >> x;
        
        if(!t) a.update(1, 1, 1 << n, x);
        if(t) b.update(1, 1, 1 << n, x);
        
        int sum = 0;
        
        for(int i = 0; i <= n; i ++) {
            for(int j = 0; j <= n; j ++) {
                int k = abs(i - j);
                sum += (f[min(i, j)] - 1) * (1 << k) * a.cnt[i] * b.cnt[j]; 
            }        
        }
        
        cout << f[n] - sum << "\n";
    }
    
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 396 KB Output is correct
8 Correct 2 ms 340 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3062 ms 93332 KB Output is correct
2 Correct 3026 ms 110828 KB Output is correct
3 Correct 2626 ms 75220 KB Output is correct
4 Correct 3118 ms 111120 KB Output is correct
5 Correct 3194 ms 110672 KB Output is correct
6 Correct 2999 ms 109492 KB Output is correct
7 Correct 3056 ms 110888 KB Output is correct
8 Correct 3097 ms 110864 KB Output is correct
9 Correct 2545 ms 73792 KB Output is correct
10 Correct 2794 ms 76324 KB Output is correct
11 Correct 2989 ms 109612 KB Output is correct
12 Correct 3155 ms 109436 KB Output is correct
13 Correct 2746 ms 76376 KB Output is correct