Submission #425486

#	Time	Username	Problem	Language	Result	Execution time	Memory
425486		KoD	Seats (IOI18_seats)	C++17	0 / 100	4083 ms	24132 KiB

seats

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

template <class T> using Vec = std::vector<T>;

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

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

int swap_seats(int a, int b) {
    if (H + W <= 2000) {
        std::swap(C[a], C[b]);
        std::swap(R[a], R[b]);
        int l = C[0], r = C[0], u = R[0], d = R[0];
        int ret = 0, cur = 0;
        while (cur < H * W) {
            l = std::min(l, C[cur]);
            r = std::max(r, C[cur]);
            u = std::min(u, R[cur]);
            d = std::max(d, R[cur]);
            if ((r - l + 1) * (d - u + 1) == cur + 1) {
                ret += 1;
                cur += 1;
            } else {
                cur = (r - l + 1) * (d - u + 1) - 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(C[a], C[b]);
        std::swap(R[a], R[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: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30