oj.uz

Submission #787317

# Submission time Handle Problem Language Result Execution time Memory
787317 2023-07-19T05:07:30 Z 이동현(#10034) 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 1097 ms 111136 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

struct Seg{
    int n;
    vector<int> col;
    vector<int> cnt;

    Seg(){}
    Seg(int m){
        n = m + 4;
        col.resize(n * 4 + 4);
        cnt.resize(24);
    }

    void push(int x, int s, int e, int pos){
        if(s == e){
            col[x] = 1 - col[x];
            return;
        }

        int mid = s + e >> 1;
        if(pos <= mid){
            push(x * 2, s, mid, pos);
        }
        else{
            push(x * 2 + 1, mid + 1, e, pos);
        }

        if(col[x] != -1) --cnt[__builtin_ctz(e - s + 1)];
        if(col[x * 2] == -1 || col[x * 2 + 1] == -1 || col[x * 2] != col[x * 2 + 1]) col[x] = -1;
        else col[x] = col[x * 2];
        if(col[x] != -1) ++cnt[__builtin_ctz(e - s + 1)];
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    vector<Seg> tr(2);
    tr[0] = tr[1] = Seg(1 << n);
    for(int i = 0; i <= n; ++i){
        tr[0].cnt[i] += (1 << (n - i));
        tr[1].cnt[i] += (1 << (n - i));
    }

    int all = 1;
    for(int i = 0; i <= n; ++i){
        all *= 4;
    }
    all = (all - 1) / 3;
    while(q--){
        int op, x;
        cin >> op >> x;
        --x;

        tr[op].push(1, 0, (1 << n) - 1, x);

        int ans = 0;
        for(int i = 0; i <= n; ++i){
            // cout << tr[0].cnt[i] << ' ' << tr[1].cnt[i] << endl;
            ans += tr[0].cnt[i] * tr[1].cnt[i];
        }
        ans = (all - ans) * 4 + 1;

        cout << ans << '\n';
    }

    return 0;
}

Compilation message

collecting.cpp: In member function 'void Seg::push(long long int, long long int, long long int, long long int)':
collecting.cpp:26:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |         int mid = s + e >> 1;
      |                   ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 340 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 1029 ms 110772 KB Output is correct
2 Correct 1028 ms 110820 KB Output is correct
3 Correct 865 ms 75180 KB Output is correct
4 Correct 1027 ms 111136 KB Output is correct
5 Correct 1067 ms 110652 KB Output is correct
6 Correct 1045 ms 109480 KB Output is correct
7 Correct 1097 ms 110792 KB Output is correct
8 Correct 1052 ms 110896 KB Output is correct
9 Correct 860 ms 73864 KB Output is correct
10 Correct 974 ms 76324 KB Output is correct
11 Correct 1082 ms 108980 KB Output is correct
12 Correct 1049 ms 109364 KB Output is correct
13 Correct 912 ms 76340 KB Output is correct