Submission #1043563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043563		Zicrus	Seats (IOI18_seats)	C++17	0 / 100	133 ms	72772 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
using namespace std;

typedef long long ll;

struct rect {
    int left, right, top, bot;

    inline int size() {
        return (right-left+1) * (bot-top+1);
    }

    inline int minSide() {
        return min(right-left+1, bot-top+1);
    }

    static rect merge(const rect &a, const rect &b) {
        return {min(a.left, b.left), max(a.right, b.right), min(a.top, b.top), max(a.bot, b.bot)};
    }
};

int n, w, h, pow2;
vector<int> x, y;
vector<rect> seg;

rect segRect(ll low, ll high) {
    low += pow2; high += pow2;
    rect res = seg[low++];
    while (low <= high) {
        if (low & 1) res = rect::merge(res, seg[low++]);
        if (!(high & 1)) res = rect::merge(res, seg[high--]);
        low /= 2; high /= 2;
    }
    return res;
}

void update(ll i) {
    i += pow2;
    i /= 2;
    while (i > 0) {
        seg[i] = rect::merge(seg[2*i], seg[2*i+1]);
        i /= 2;
    }
}

void give_initial_chart(int h1, int w1, vector<int> r, vector<int> c) {
    w = w1; h = h1;
    n = h*w;
    x = c; y = r;

    pow2 = 1ll << (ll)ceil(log2(n));
    seg = vector<rect>(2*pow2);
    for (int i = pow2; i < pow2+n; i++) {
        seg[i] = {x[i-pow2], x[i-pow2], y[i-pow2], y[i-pow2]};
    }
    for (int i = pow2-1; i > 0; i--) {
        seg[i] = rect::merge(seg[2*i], seg[2*i+1]);
    }
}

int swap_seats(int a, int b) {
    swap(x[a], x[b]);
    swap(y[a], y[b]);
    update(a);
    update(b);
    int res = 0;
    rect r = {x[0], x[0], y[0], y[0]};
    int i = 0;
    while (i < n) {
        if (r.size() == i+1) {
            res++;
            int nw = r.size() + r.minSide() - 1;
            r = rect::merge(r, segRect(i+1, nw));
            i = nw;
        }
        else {
            int nw = r.size() - 1;
            r = rect::merge(r, segRect(i+1, nw));
            i = nw;
        }
    }
    return res;
}

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