oj.uz

답안 #377770

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
377770 2021-03-15T03:00:58 Z RyoPham 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 1984 ms 70252 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct

Subtask #3
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1960 ms 69984 KB Output is correct
2 Correct 1984 ms 70024 KB Output is correct
3 Correct 1819 ms 54796 KB Output is correct
4 Correct 1976 ms 70252 KB Output is correct
5 Correct 1928 ms 69760 KB Output is correct
6 Correct 1920 ms 68744 KB Output is correct
7 Correct 1920 ms 70172 KB Output is correct
8 Correct 1957 ms 70076 KB Output is correct
9 Correct 1717 ms 53484 KB Output is correct
10 Correct 1792 ms 56164 KB Output is correct
11 Correct 1836 ms 68588 KB Output is correct
12 Correct 1894 ms 68716 KB Output is correct
13 Correct 1763 ms 55916 KB Output is correct