oj.uz

Submission #821786

# Submission time Handle Problem Language Result Execution time Memory
821786 2023-08-11T16:32:43 Z nonono 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 2397 ms 93704 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 ++) {
            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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 320 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 2 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 328 KB Output is correct
7 Correct 2 ms 324 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 2310 ms 93364 KB Output is correct
2 Correct 2327 ms 93404 KB Output is correct
3 Correct 2011 ms 58536 KB Output is correct
4 Correct 2330 ms 93704 KB Output is correct
5 Correct 2312 ms 93240 KB Output is correct
6 Correct 2219 ms 92136 KB Output is correct
7 Correct 2323 ms 93508 KB Output is correct
8 Correct 2397 ms 93436 KB Output is correct
9 Correct 1977 ms 60668 KB Output is correct
10 Correct 2066 ms 59344 KB Output is correct
11 Correct 2224 ms 92568 KB Output is correct
12 Correct 2258 ms 92032 KB Output is correct
13 Correct 2000 ms 59072 KB Output is correct