oj.uz

Submission #821799

# Submission time Handle Problem Language Result Execution time Memory
821799 2023-08-11T17:14:04 Z nonono 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 2286 ms 93740 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];
         	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.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 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 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 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 328 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2225 ms 93344 KB Output is correct
2 Correct 2201 ms 93424 KB Output is correct
3 Correct 1895 ms 58608 KB Output is correct
4 Correct 2241 ms 93740 KB Output is correct
5 Correct 2286 ms 93180 KB Output is correct
6 Correct 2160 ms 92172 KB Output is correct
7 Correct 2238 ms 93464 KB Output is correct
8 Correct 2222 ms 93528 KB Output is correct
9 Correct 1873 ms 59776 KB Output is correct
10 Correct 2012 ms 59300 KB Output is correct
11 Correct 2241 ms 92592 KB Output is correct
12 Correct 2182 ms 92160 KB Output is correct
13 Correct 1965 ms 59092 KB Output is correct