Submission #377770

#	Time	Username	Problem	Language	Result	Execution time	Memory
377770		RyoPham	즐거운 사진 수집 (JOI13_collecting)	C++17	100 / 100	1984 ms	70252 KiB

collecting

#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 2e6 + 5;
const int logn = 22;

int n, Q;

struct segment_tree
{
    int cnt_one[maxn * 4], cnt_diff[logn];
    int leaf_id[maxn];

    void build(int x, int l, int r)
    {
        if(l == r)
        {
            leaf_id[l] = x;
            return;
        }
        int mid = (l + r) / 2;
        build(x * 2, l, mid);
        build(x * 2 + 1, mid + 1, r);
    }

    void update(int x, int l, int r, int p, int lv)
    {
        if(l == r)
        {
            cnt_one[x] ^= 1;
            return;
        }
        int mid = (l + r) / 2;
        if(p <= mid) update(x * 2, l, mid, p, lv + 1);
        else update(x * 2 + 1, mid + 1, r, p, lv + 1);
        if(cnt_one[x] > 0 && cnt_one[x] < r - l + 1)
            --cnt_diff[lv];
        cnt_one[x] = cnt_one[x * 2] + cnt_one[x * 2 + 1];
        if(cnt_one[x] > 0 && cnt_one[x] < r - l + 1)
            ++cnt_diff[lv];
    }
} row_data, col_data;

void read_input()
{
    cin >> n >> Q;
    cerr << n << ' ' << Q;
}

void query(segment_tree&row, segment_tree&col, int x, lli&k)
{
    int lv = n, cur_size = 1, cur = row.leaf_id[x];
    while(lv >= 0)
    {
        if(row.cnt_one[cur] > 0 && row.cnt_one[cur] < cur_size)
            k -= (1 << lv);
        else k -= col.cnt_diff[lv];
        --lv;
        cur /= 2;
        cur_size *= 2;
    }
    row.update(1, 1, (1 << n), x, 0);
    lv = n; cur_size = 1; cur = row.leaf_id[x];
    while(lv >= 0)
    {
        if(row.cnt_one[cur] > 0 && row.cnt_one[cur] < cur_size)
            k += (1 << lv);
        else k += col.cnt_diff[lv];
        --lv;
        cur /= 2;
        cur_size *= 2;
    }
}

void solve()
{
    row_data.build(1, 1, (1 << n));
    col_data.build(1, 1, (1 << n));
    lli k = 0;
    for(; Q > 0; --Q)
    {
        int type, x;
        cin >> type >> x;
        if(type == 0)
            query(row_data, col_data, x, k);
        else
            query(col_data, row_data, x, k);
        cout << k * 4 + 1 << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    solve();
}

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