Submission #821799

#	Time	Username	Problem	Language	Result	Execution time	Memory
821799		nonono	즐거운 사진 수집 (JOI13_collecting)	C++14	100 / 100	2286 ms	93740 KiB

collecting

#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];
         	cnt[k] ++ ;
            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 ++) {
            sum += (f[i] - 1) * a.cnt[i] * b.cnt[i]; 
            
            for(int j = i + 1; j <= n; j ++) {
                int k = abs(i - j);
                sum += (f[i] - 1) * (1 << k) * a.cnt[i] * b.cnt[j]; 
                sum += (f[i] - 1) * (1 << k) * a.cnt[j] * b.cnt[i];
            }        
        }
        
        cout << f[n] - sum << "\n";
    }
    
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70