제출 #1247747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247747		makmed1337	자리 배치 (IOI18_seats)	C++20	11 / 100	4098 ms	86836 KiB

seats

#include "seats.h"
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>

using namespace std;

constexpr int inf = 1e9;
struct Tree {
    struct T {
        int mn = inf, mx = -inf;
        static T from(int x) { return {x, x}; }
        T static combine(T f, T s) { return {min(f.mn, s.mn), max(f.mx, s.mx)}; }
    };

    vector<T> tree;
    void pull(int i) { tree[i] = T::combine(tree[2 * i], tree[2 * i + 1]); }

    void init(vector<int> const &base) {
        int n = base.size();
        tree.resize(4 * n);
        _build(1, 0, n - 1, base);
    }

    void _build(int i, int l, int r, vector<int> const &base) {
        if (l == r) {
            tree[i] = T::from(base[l]);
            return;
        }

        int m = (l + r) / 2;
        _build(2 * i, l, m, base);
        _build(2 * i + 1, m + 1, r, base);
        pull(i);
    }

    T get(int i, int l, int r, int lb, int rb) const {
        if (r < lb || l > rb) {
            return {};
        }

        if (lb <= l && r <= rb) {
            return tree[i];
        }

        int m = (l + r) / 2;
        return T::combine(get(2 * i, l, m, lb, rb), get(2 * i + 1, m + 1, r, lb, rb));
    }

    void update(int i, int l, int r, int pos, int x) {
        if (pos < l || pos > r) {
            return;
        }

        if (l == r) {
            tree[i] = T::from(x);
            return;
        }

        int m = (l + r) / 2;
        update(2 * i, l, m, pos, x);
        update(2 * i + 1, m + 1, r, pos, x);
        pull(i);
    }
};

vector<pair<int, int>> pos;
Tree rt, ct;
int n;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H * W;
    pos.resize(n);
    for (int i = 0; i < n; i++) {
        pos[i] = {R[i], C[i]};
    }
    rt.init(R);
    ct.init(C);
}

int swap_seats(int a, int b) {
    swap(pos[a], pos[b]);
    pair<int, int> rr{1e9, -1}, cc{1e9, -1};
    int res = 0;
    for (int i = 0; i < n; i++) {
        rr.first = min(rr.first, pos[i].first);
        rr.second = max(rr.second, pos[i].first);

        cc.first = min(cc.first, pos[i].second);
        cc.second = max(cc.second, pos[i].second);

        res += (rr.second - rr.first + 1) * (cc.second - cc.first + 1) == i + 1;
    }

    return res;
    // rt.update(1, 0, n - 1, a, r[a]);
    // rt.update(1, 0, n - 1, b, r[b]);
    //
    // ct.update(1, 0, n - 1, a, c[a]);
    // ct.update(1, 0, n - 1, b, c[b]);
    //
    //
    // int res = 0;
    // int i = 0;
    // while (i < n) {
    //     auto rr = rt.get(1, 0, n - 1, 0, i);
    //     auto cc = ct.get(1, 0, n - 1, 0, i);
    //     int sz = (rr.mx - rr.mn + 1) * (cc.mx - cc.mn + 1);
    //     if (sz == i + 1) {
    //         res++;
    //         ++i;
    //     } else {
    //         i = sz - 1;
    //     }
    // }
    // return res;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30