Submission #425496

#	Time	Username	Problem	Language	Result	Execution time	Memory
425496		KoD	Seats (IOI18_seats)	C++17	37 / 100	4033 ms	71216 KiB

seats

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

template <class T> using Vec = std::vector<T>;
constexpr int INF = std::numeric_limits<int>::max() / 2;

struct RMQ {
    int size;
    Vec<int> min, max;
    RMQ() = default;
    RMQ(const Vec<int>& vec): size(vec.size()), min(2 * vec.size(), INF), max(2 * vec.size(), INF) {
        for (int i = 0; i < size; ++i) {
            assign(i, vec[i]);
        }
    }
    void assign(int i, const int x) {
        i += size;
        min[i] = max[i] = x;
        while (i > 1) {
            i >>= 1;
            min[i] = std::min(min[2 * i], min[2 * i + 1]);
            max[i] = std::max(max[2 * i], max[2 * i + 1]);
        }
    }
    int diff(int l, int r) const {
        l += size;
        r += size;
        int x = INF, y = -INF;
        while (l < r) {
            if (l & 1) {
                x = std::min(x, min[l]);
                y = std::max(y, max[l]);
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                x = std::min(x, min[r]);
                y = std::max(y, max[r]);
            }
            l >>= 1;
            r >>= 1;
        }
        return y - x + 1;
    }
};

namespace {
    int H, W;
    Vec<int> R, C;
    RMQ row, col;
};

void give_initial_chart(int h, int w, Vec<int> r, Vec<int> c) {
    H = h, W = w;
    R = r, C = c;
    row = RMQ(R), col = RMQ(C);
}

int swap_seats(int a, int b) {
    if (H + W <= 2000) {
        std::swap(R[a], R[b]);
        std::swap(C[a], C[b]);
        row.assign(a, R[a]);
        col.assign(a, C[a]);
        row.assign(b, R[b]);
        col.assign(b, C[b]);        
        int ret = 0, cur = 0;
        while (cur < H * W) {
            const int area = row.diff(0, cur + 1) * col.diff(0, cur + 1);
            if (area == cur + 1) {
                ret += 1;
                cur += 1;
            } else {
                cur = area - 1;                
            }
        }
        return ret;
    } else {
        static int sum = -1;
        static Vec<int> left, right, up, down;
        if (sum == -1) {
            left = right = up = down = Vec<int>(H * W);
            sum = 0;
            for (int i = 0; i < H * W; ++i) {
                left[i] = right[i] = C[i];
                up[i] = down[i] = R[i];
                if (i > 0) {
                    left[i] = std::min(left[i], left[i - 1]);
                    right[i] = std::max(right[i], right[i - 1]);
                    up[i] = std::min(up[i], up[i - 1]);
                    down[i] = std::max(down[i], down[i - 1]);
                }
                sum += ((right[i] - left[i] + 1) * (down[i] - up[i] + 1) == i + 1);
            }            
        }
        if (a > b) {
            std::swap(a, b);
        }
        for (int i = a; i <= b; ++i) {
            sum -= ((right[i] - left[i] + 1) * (down[i] - up[i] + 1) == i + 1);
        }
        std::swap(R[a], R[b]);
        std::swap(C[a], C[b]);
        for (int i = a; i <= b; ++i) {
            left[i] = right[i] = C[i];
            up[i] = down[i] = R[i];
            if (i > 0) {
                left[i] = std::min(left[i], left[i - 1]);
                right[i] = std::max(right[i], right[i - 1]);
                up[i] = std::min(up[i], up[i - 1]);
                down[i] = std::max(down[i], down[i - 1]);
            }
            sum += ((right[i] - left[i] + 1) * (down[i] - up[i] + 1) == i + 1);
        }   
        return sum;
    }
}

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