Submission #991382

#	Time	Username	Problem	Language	Result	Execution time	Memory
991382		Forested	Seats (IOI18_seats)	C++17	17 / 100	563 ms	64716 KiB

seats

#include <bits/stdc++.h>
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r) - 1; i >= (i32)(l); --i)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define LEN(x) (i32)(x).size()
#define ALL(x) begin(x), end(x)
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

#include "seats.h"

using Rect = tuple<i32, i32, i32, i32>;

i32 h, w;
V<i32> r, c;
V<Rect> rect;
i32 ans;

i32 get_size(const Rect &rect) {
    auto [u, d, l, r] = rect;
    return (d - u) * (r - l);
}

Rect add_point(const Rect &rect, i32 x, i32 y) {
    auto [u, d, l, r] = rect;
    chmin(u, x);
    chmax(d, x + 1);
    chmin(l, y);
    chmax(r, y + 1);
    return Rect(u, d, l, r);
}

void give_initial_chart(i32 _h, i32 _w, V<i32> _r, V<i32> _c) {
    h = _h;
    w = _w;
    r = _r;
    c = _c;
    rect.resize(h * w);
    rect[0] = Rect(r[0], r[0] + 1, c[0], c[0] + 1);
    REP(i, 1, h * w) {
        rect[i] = add_point(rect[i - 1], r[i], c[i]);
    }
    ans = 1;
    REP(i, h * w - 1) {
        if (get_size(rect[i]) == i + 1) {
            ++ans;
        }
    }
}

i32 swap_seats(i32 a, i32 b) {
    if (a > b) {
        swap(a, b);
    }
    assert(b - a <= 10000);
    REP(i, a, b) {
        if (get_size(rect[i]) == i + 1) {
            --ans;
        }
    }
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    REP(i, a, b) {
        if (i == 0) {
            rect[i] = Rect(r[i], r[i] + 1, c[i], c[i] + 1);
        } else {
            rect[i] = add_point(rect[i - 1], r[i], c[i]);
        }
        if (get_size(rect[i]) == i + 1) {
            ++ans;
        }
    }
    return ans;
}

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