제출 #1237588

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237588		bangan	모자이크 (IOI24_mosaic)	C++20	0 / 100	188 ms	16320 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;

#define ll long long

#define pb push_back

#define LC (v<<1)
#define RC (v<<1|1)
#define mid ((l+r) >> 1)

const int N = 200200;

int L, R;
int sum[4 * 2*N];
int st[4 * 2*N];

void Init(int i, int x, int y, int v=1, int l=0, int r = 2*N) {
    if (r-l == 1) {
        sum[v] = x;
        st[v] = y;
        return;
    }
    i<mid ? Init(i,x,y, LC, l, mid) : Init(i,x,y, RC, mid, r);
    sum[v] = sum[LC] + sum[RC];
}

int Get(int x, int v=1, int l=0, int r = 2*N) {
    if (r-l == 1) return st[v] ^ (x%2);
    if (0 <= x-sum[LC]) return Get(x-sum[LC], RC, mid, r);
    else return Get(x, LC, l, mid);
}

int Update(int i, int x, int y, int v=1, int l=0, int r = 2*N) {
    if (r-l == 1) {
        sum[v] += x;
        st[v] ^= y;
        return sum[v]==0;
    }
    int ret = (i<mid ? Update(i,x,y, LC, l, mid) : Update(i,x,y, RC, mid, r));
    sum[v] = sum[LC] + sum[RC];
    return ret;
}

std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> LE, std::vector<int> RI) {
	int n = X.size();
	int q = (int)T.size();
    if (n==1) return vector<ll> (q, X[0]);
    vector<int> row;
    row.pb((X[1] | Y[1]) ^ 1);
    for (int i=2; i<n; i++) row.pb((row.back() | X[i]) ^ 1);
    L=n;
    R=n;
    for (int i=0; i < n-1;) {
        int j = i+1;
        while (j < n-1 && row[j-1] != row[j]) j++;
        Init(R++, j-i, row[i]);
        i=j;
    }
    vector<ll> all(q), ans(q);
    iota(all.begin(), all.end(), 0);
    sort(all.begin(), all.end(), [&](int i, int j) {
        return T[i]<T[j];
    });
    auto it = all.begin();
    while (it != all.end() && T[*it]==0) {
        ans[*it] = X[LE[*it]];
        it++;
    }
    for (int r=1; r<n; ) {
        while (it!=all.end() && T[*it]==r) {
            int c = LE[*it];
            if (c==0) ans[*it] = Y[r];
            else ans[*it] = Get(c-1);
            it++;
        }
        r++;
        if (r != n) {
            if (Update(R, -1, 0)) R--;
            int x = Get(0);
            if (x==1 || (x==0 && Y[r]==0)) Update(L, 1, 1);
            else {
                L--;
                Init(L, 1, 0);
            }
        }
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 8
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22