Submission #821798

#	Time	Username	Problem	Language	Result	Execution time	Memory
821798		nonono	즐거운 사진 수집 (JOI13_collecting)	C++14	0 / 100	1686 ms	92144 KiB

collecting

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
const int mxN = 20;
 
int n, q;
int f[mxN + 5], dp1[mxN + 5], dp2[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] ++ ;
        }
    }
};
 
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 = n; i >= 0; i --) dp1[i] = dp1[i + 1] * 2 + a.cnt[i];
        for(int i = n; i >= 0; i --) dp2[i] = dp2[i + 1] * 2 + b.cnt[i];
        
        for(int i = 0; i <= n; i ++) {
            if(a.cnt[i] > 0) sum += (f[i] - 1) * a.cnt[i] * dp2[i];
            if(b.cnt[i] > 0) sum += (f[i] - 1) * b.cnt[i] * dp1[i];
            if(a.cnt[i] > 0 && b.cnt[i] > 0) sum -= (f[i] - 1) * a.cnt[i] * b.cnt[i];
        }
        
        cout << f[n] - sum << "\n";
    }
    
    return 0;
}

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