Submission #138192

#	Time	Username	Problem	Language	Result	Execution time	Memory
138192		fredbr	Seats (IOI18_seats)	C++17	31 / 100	4074 ms	114164 KiB

seats

#include "seats.h"

#include <bits/stdc++.h>

using namespace std;

int const inf = 0x3f3f3f3f;

using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vector<int>>;

int n, m;
vii pos;
vvi v;

struct Seg {
    int n;
    vector<int> tree;
    vector<int> const& v;

    Seg(vi const& v) : n(v.size()), tree(n*4), v(v) {
        build(0, 0, n-1);
    };

    void build(int no, int l, int r) {
        if (l == r) return void(tree[no] = v[l]);
        int m = (l+r)/2;
        build(no*2+1, l, m);
        build(no*2+2, m+1, r);

        tree[no] = max(tree[no*2+1], tree[no*2+2]);
    }

    void upd(int no, int l, int r, int pos, int val) {
        if (l == r) return void(tree[no] = val);

        int m = (l+r)/2;

        if (pos <= m) upd(no*2+1, l, m, pos, val);
        else upd(no*2+2, m+1, r, pos, val);

        tree[no] = max(tree[no*2+1], tree[no*2+2]);
    }

    int get(int no, int l, int r, int a, int b) {
        if (a <= l and r <= b) return tree[no];

        int m = (l+r)/2;

        if (b <= m) return get(no*2+1, l, m, a, b);
        if (a > m) return get(no*2+2, m+1, r, a, b);

        return max(get(no*2+1, l, m, a, b),
                   get(no*2+2, m+1, r, a, b));
    }
};

vector<Seg> rows, cols;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H, m = W;

    v = vvi(n, vi(m));

    for (int i = 0; i < n*m; i++) {
        v[R[i]][C[i]] = i;
        pos.emplace_back(R[i], C[i]);
    }

    for (int i = 0; i < n; i++) {
        rows.emplace_back(v[i]);
    }

    vector<int> col;
    for (int i = 0; i < m; i++) {
        col.clear();
        for (int j = 0; j < n; j++) {
            col.push_back(v[j][i]);
        }
        cols.emplace_back(col);
    }
}

int swap_seats(int a, int b) {
    swap(pos[a], pos[b]);

    rows[pos[a].first].upd(0, 0, m-1, pos[a].second, a);
    rows[pos[b].first].upd(0, 0, m-1, pos[b].second, b);

    cols[pos[a].second].upd(0, 0, n-1, pos[a].first, a);
    cols[pos[b].second].upd(0, 0, n-1, pos[b].first, b);

    int x1, x2, y1, y2;
    x1 = x2 = pos[0].first;

    y1 = y2 = pos[0].second;

    int max_at = 0;
    int ans = 1;

    struct Result {
        int maxi, x1, x2, y1, y2;

        bool operator<(Result const& rhs) const {
            return maxi < rhs.maxi;
        }
    };

    Result rs[4];

    for (int i = 1; i < n + m - 1; i++) {
        fill(rs, rs+4, Result{inf, 0, 0, 0, 0});

        if (x1 > 0)
            rs[0] = {max(max_at, rows[x1-1].get(0, 0, m-1, y1, y2)),
                     x1-1, x2, y1, y2};

        if (x2+1 < n)
            rs[1] = {max(max_at, rows[x2+1].get(0, 0, m-1, y1, y2)),
                     x1, x2+1, y1, y2};

        if (y1 > 0)
            rs[2] = {max(max_at, cols[y1-1].get(0, 0, n-1, x1, x2)),
                     x1, x2, y1-1, y2};
        if (y2+1 < m)
            rs[3] = {max(max_at, cols[y2+1].get(0, 0, n-1, x1, x2)),
                     x1, x2, y1, y2+1};

        Result res = *min_element(rs, rs+4);

        x1 = res.x1;
        x2 = res.x2;
        y1 = res.y1;
        y2 = res.y2;

        max_at = res.maxi;

        if (max_at == (x2-x1+1)*(y2-y1+1) - 1) ans++;
    }

    return ans;
}

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