Submission #709973

#	Time	Username	Problem	Language	Result	Execution time	Memory
709973		KoD	Seats (IOI18_seats)	C++17	100 / 100	2558 ms	69120 KiB

seats

#include "seats.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <numeric>
#include <limits>
#include <iterator>

namespace kod {

using std::cerr;
using std::endl;
using std::vector;
using std::pair;
using std::begin;
using std::end;

constexpr int inf = std::numeric_limits<int>::max() / 2;

struct info {
    int min, count;
    static info id() { return {inf, 0}; }
};

class lazy_segtree {
  public:
    lazy_segtree() = default;

    explicit lazy_segtree(const int n) {
        logn = 0;
        while ((1 << logn) < n) logn += 1;
        size = 1 << logn;
        data.resize(2 * size, info::id());
        lazy.resize(size);
        for (int i = 0; i < n; ++i) {
            data[i + size] = {0, 1};
        }
        for (int i = size - 1; i > 0; --i) {
            fetch(i);
        }
    }

    void add(int l, int r, const int x) {
        l += size;
        r += size;
        push(l);
        push(r);
        const int lc = l;
        const int rc = r;
        while (l < r) {
            if (l & 1) apply(l++, x);
            if (r & 1) apply(--r, x);
            l >>= 1;
            r >>= 1;
        }
        pull(lc);
        pull(rc);
    }

    info get() const {
        return data[1];
    }

  private:
    int size, logn;
    vector<info> data;
    vector<int> lazy;

    void apply(const int i, const int e) {
        data[i].min += e;
        if (i < size) lazy[i] += e;
    }

    void fetch(const int i) {
        const auto& l = data[2 * i + 0];
        const auto& r = data[2 * i + 1];
        const int m = std::min(l.min, r.min);
        data[i].min = m;
        data[i].count = (m == l.min ? l.count : 0) + (m == r.min ? r.count : 0);
    }

    void flush(const int i) {
        apply(2 * i + 0, lazy[i]);
        apply(2 * i + 1, lazy[i]);
        lazy[i] = 0;
    }

    void push(const int i) {
        const int lsb = __builtin_ctz(i);
        for (int d = logn; d > lsb; --d) {
            flush(i >> d);
        }
    }

    void pull(int i) {
        i >>= __builtin_ctz(i);
        while (i > 1) fetch(i >>= 1);
    }
};

int N, H, W;
vector<int> id, grid;
lazy_segtree seg;

void update(const int x, const int c) {
    vector<int> list;
    for (const int a : {0, 1}) {
        for (const int b : {0, W}) {
            list.push_back(grid[x + a + b]);
        }
    }
    std::sort(begin(list), end(list));
    seg.add(list[0], list[1], c);
    seg.add(list[2], list[3], c);
}

void init() {
    grid.resize(H * W, N);
    for (int i = 0; i < N; ++i) {
        grid[id[i]] = i;
    }
    seg = lazy_segtree(N);
    for (int i = 0; i < H - 1; ++i) {
        for (int j = 0; j < W - 1; ++j) {
            update(i * W + j, 1);
        }
    }
}

void cell(const int x, const int a) {
    for (const int a : {0, 1}) {
        for (const int b : {0, W}) {
            update(x - a - b, -1);
        }
    }
    grid[x] = a;
    id[a] = x;
    for (const int a : {0, 1}) {
        for (const int b : {0, W}) {
            update(x - a - b, 1);
        }
    }
}

int swap(const int a, const int b) {
    const int x = id[a];
    const int y = id[b];
    cell(x, b);
    cell(y, a);
    const auto ret = seg.get();
    return ret.min == 4 ? ret.count : 0;
}

}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    kod::N = H * W;
    kod::H = H + 2;
    kod::W = W + 2;
    kod::id.resize(H * W);
    for (int i = 0; i < H * W; ++i) {
        kod::id[i] = (R[i] + 1) * (W + 2) + (C[i] + 1);
    }
    kod::init();
}

int swap_seats(int a, int b) {
    return kod::swap(a, b);
}

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