結果

問題 No.3327 うるせぇ、ポリオミノぶつけんぞ
コンテスト
ユーザー urunea
提出日時 2025-11-05 16:09:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,390 bytes
コンパイル時間 3,771 ms
コンパイル使用メモリ 303,016 KB
実行使用メモリ 62,764 KB
最終ジャッジ日時 2025-11-05 16:09:50
合計ジャッジ時間 10,491 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 3 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL << 60);

struct LazySegTree {
    int n;
    vector<ll> minv, maxv, lazy;
    vector<int> min_idx, max_idx;

    LazySegTree(int N) {
        n = 1;
        while (n < N) n <<= 1;
        minv.assign(2 * n, INF);
        maxv.assign(2 * n, -INF);
        lazy.assign(2 * n, 0);
        min_idx.resize(2 * n);
        max_idx.resize(2 * n);
        for (int i = 0; i < n; i++) {
            min_idx[n + i] = i + 1;
            max_idx[n + i] = i + 1;
        }
        for (int i = n - 1; i >= 1; i--) pull(i);
    }

    void pull(int k) {
        if (minv[k * 2] <= minv[k * 2 + 1]) {
            minv[k] = minv[k * 2];
            min_idx[k] = min_idx[k * 2];
        } else {
            minv[k] = minv[k * 2 + 1];
            min_idx[k] = min_idx[k * 2 + 1];
        }

        if (maxv[k * 2] >= maxv[k * 2 + 1]) {
            maxv[k] = maxv[k * 2];
            max_idx[k] = max_idx[k * 2];
        } else {
            maxv[k] = maxv[k * 2 + 1];
            max_idx[k] = max_idx[k * 2 + 1];
        }
    }

    void apply(int k, ll v) {
        minv[k] += v;
        maxv[k] += v;
        if (k < n) lazy[k] += v;
    }

    void push(int k) {
        if (lazy[k] != 0) {
            apply(k * 2, lazy[k]);
            apply(k * 2 + 1, lazy[k]);
            lazy[k] = 0;
        }
    }

    void range_add(int a, int b, ll v) { range_add(a, b, v, 1, 1, n); }
    void range_add(int a, int b, ll v, int k, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) {
            apply(k, v);
            return;
        }
        push(k);
        int mid = (l + r) / 2;
        range_add(a, b, v, k * 2, l, mid);
        range_add(a, b, v, k * 2 + 1, mid + 1, r);
        pull(k);
    }

    pair<ll, int> range_min(int a, int b) { return range_min(a, b, 1, 1, n); }
    pair<ll, int> range_min(int a, int b, int k, int l, int r) {
        if (b < l || r < a) return {INF, -1};
        if (a <= l && r <= b) return {minv[k], min_idx[k]};
        push(k);
        int mid = (l + r) / 2;
        auto L = range_min(a, b, k * 2, l, mid);
        auto R = range_min(a, b, k * 2 + 1, mid + 1, r);
        return (L.first <= R.first ? L : R);
    }

    pair<ll, int> range_max(int a, int b) { return range_max(a, b, 1, 1, n); }
    pair<ll, int> range_max(int a, int b, int k, int l, int r) {
        if (b < l || r < a) return {-INF, -1};
        if (a <= l && r <= b) return {maxv[k], max_idx[k]};
        push(k);
        int mid = (l + r) / 2;
        auto L = range_max(a, b, k * 2, l, mid);
        auto R = range_max(a, b, k * 2 + 1, mid + 1, r);
        return (L.first >= R.first ? L : R);
    }

    void point_set(int pos, ll val) { point_set(pos, val, 1, 1, n); }
    void point_set(int pos, ll val, int k, int l, int r) {
        if (l == r) {
            minv[k] = maxv[k] = val;
            lazy[k] = 0;
            return;
        }
        push(k);
        int mid = (l + r) / 2;
        if (pos <= mid)
            point_set(pos, val, k * 2, l, mid);
        else
            point_set(pos, val, k * 2 + 1, mid + 1, r);
        pull(k);
    }

    ll point_get(int pos) { return point_get(pos, 1, 1, n); }
    ll point_get(int pos, int k, int l, int r) {
        if (l == r) return minv[k];
        push(k);
        int mid = (l + r) / 2;
        if (pos <= mid)
            return point_get(pos, k * 2, l, mid);
        else
            return point_get(pos, k * 2 + 1, mid + 1, r);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vector<ll> A(N);
    for (auto &x : A) cin >> x;

    vector<array<ll, 3>> mem;
    mem.reserve(N);
    for (int i = 0; i < N; i++) mem.push_back({A[i], i + 1, 0});
    sort(mem.begin(), mem.end());

    for (int i = 0; i < N; i++) mem[i][2] = i + 1; // sidx = 1-based index

    LazySegTree segm(N), segM(N);
    vector<array<ll, 3>> L = mem;
    unordered_map<int, array<ll, 3>> d;

    for (int i = 0; i < N; i++) {
        segm.point_set(i + 1, L[i][1]);
        segM.point_set(i + 1, L[i][1]);
        d[i + 1] = L[i];
    }

    vector<ll> ans;

    for (int _ = 0; _ < Q; _++) {
        int c;
        ll X;
        cin >> c >> X;
        // bisect_left
        int idx = lower_bound(L.begin(), L.end(), array<ll, 3>{X + 1, -100, -100}) - L.begin();
        if (idx == (int)L.size()) {
            ans.push_back(-1);
            continue;
        }

        ll num = L[idx][0];
        ll j = L[idx][1];
        ll sidx = L[idx][2];

        if (c == 1) {
            auto [res, seg_idx] = segm.range_min(sidx, N);
            if (res == -1 || res == 1000000000)
                ans.push_back(-1);
            else {
                ans.push_back(res);
                segm.point_set(seg_idx, 1000000000);
                segM.point_set(seg_idx, -1);
                L.erase(L.begin() + seg_idx - 1);
            }
        } else {
            auto [res, seg_idx] = segM.range_max(sidx, N);
            if (res == -1 || res == 1000000000)
                ans.push_back(-1);
            else {
                ans.push_back(res);
                segm.point_set(seg_idx, 1000000000);
                segM.point_set(seg_idx, -1);
                L.erase(L.begin() + seg_idx - 1);
            }
        }
    }

    for (auto x : ans) cout << x << "\n";
}
0