Submission #98619

#	Time	Username	Problem	Language	Result	Execution time	Memory
98619		eriksuenderhauf	Seats (IOI18_seats)	C++11	31 / 100	4021 ms	84444 KiB

seats

#pragma GCC optimize("O3")
#include "seats.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int INF = 1e9 + 7;
const int MAXN = 1e3 + 5;
int tree[3 * MAXN][3 * MAXN];
int arr[MAXN][MAXN];
pair<int,int> pos[MAXN * MAXN];
int h = 0, w = 0;

array<int, 4> tree1d[3 * MAXN * MAXN];

void build(int l, int r, int k) {
    if (l == r) {
        tree1d[k][0] = pos[l].fi;
        tree1d[k][1] = pos[l].se;
        tree1d[k][2] = pos[r].fi;
        tree1d[k][3] = pos[r].se;
        return;
    }
    int m = (l + r) / 2;
    build(m + 1, r, k * 2 + 1);
    build(l, m, k * 2);
    tree1d[k][0] = min(tree1d[k * 2][0], tree1d[k * 2 + 1][0]);
    tree1d[k][1] = min(tree1d[k * 2][1], tree1d[k * 2 + 1][1]);
    tree1d[k][2] = max(tree1d[k * 2][2], tree1d[k * 2 + 1][2]);
    tree1d[k][3] = max(tree1d[k * 2][3], tree1d[k * 2 + 1][3]);
}

array<int,4> qry(int l, int r, int k, int a) {
    if (r < 0 || a < l) {
        array<int,4> ret;
        ret[0] = INF;
        ret[1] = INF;
        ret[2] = -1;
        ret[3] = -1;
        return ret;
    }
    if (0 <= l && r <= a)
        return tree1d[k];
    int m = (l + r) / 2;
    array<int,4> x = qry(l, m, k * 2, a);
    array<int,4> y = qry(m + 1, r, k * 2 + 1, a);
    x[0] = min(x[0], y[0]);
    x[1] = min(x[1], y[1]);
    x[2] = max(x[2], y[2]);
    x[3] = max(x[3], y[3]);
    return x;
}

void upd(int l, int r, int k, int a) {
    if (r < a || a < l)
        return;
    if (a <= l && r <= a) {
        tree1d[k][0] = pos[l].fi;
        tree1d[k][1] = pos[l].se;
        tree1d[k][2] = pos[r].fi;
        tree1d[k][3] = pos[r].se;
        return;
    }
    int m = (l + r) / 2;
    if (m >= a)
        upd(l, m, k * 2, a);
    if (m + 1 <= a)
        upd(m + 1, r, k * 2 + 1, a);
    tree1d[k][0] = min(tree1d[k * 2][0], tree1d[k * 2 + 1][0]);
    tree1d[k][1] = min(tree1d[k * 2][1], tree1d[k * 2 + 1][1]);
    tree1d[k][2] = max(tree1d[k * 2][2], tree1d[k * 2 + 1][2]);
    tree1d[k][3] = max(tree1d[k * 2][3], tree1d[k * 2 + 1][3]);
}

void prop(int l, int r, int k, int ind) {
    if (l == r) {
        tree[ind][k] = max(tree[ind * 2][k], tree[ind * 2 + 1][k]);
        return;
    }
    int m = (l + r) / 2;
    prop(l, m, k * 2, ind);
    prop(m + 1, r, k * 2 + 1, ind);
    tree[ind][k] = max(tree[ind][k * 2], tree[ind][k * 2 + 1]);
}

void prop(int l, int r, int k, int ind, int x) {
    if (r < x || x < l)
        return;
    if (x <= l && r <= x) {
        tree[ind][k] = max(tree[ind * 2][k], tree[ind * 2 + 1][k]);
        return;
    }
    int m = (l + r) / 2;
    prop(l, m, k * 2, ind, x);
    prop(m + 1, r, k * 2 + 1, ind, x);
    tree[ind][k] = max(tree[ind][k * 2], tree[ind][k * 2 + 1]);
}

void build1(int l, int r, int k, int k2, int ind) {
    if (l == r) {
        tree[k2][k] = arr[ind][l];
        return;
    }
    int m = (l + r) / 2;
    build1(l, m, k * 2, k2, ind);
    build1(m + 1, r, k * 2 + 1, k2, ind);
    tree[k2][k] = max(tree[k2][k * 2], tree[k2][k * 2 + 1]);
}

void build2(int l, int r, int k) {
    if (l == r) {
        build1(0, w - 1, 1, k, l);
        return;
    }
    int m = (l + r) / 2;
    build2(l, m, k * 2);
    build2(m + 1, r, k * 2 + 1);
    prop(0, w - 1, 1, k);
}

int qry1(int l, int r, int k, int ind, int c, int d) {
    if (r < c || d < l)
        return 0;
    if (c <= l && r <= d)
        return tree[ind][k];
    int m = (l + r) / 2;
    return max(qry1(l, m, k * 2, ind, c, d), qry1(m + 1, r, k * 2 + 1, ind, c, d));
}

int qry2(int l, int r, int k, int a, int b, int c, int d) {
    if (r < a || b < l)
        return 0;
    if (a <= l && r <= b)
        return qry1(0, w - 1, 1, k, c, d);
    int m = (l + r) / 2;
    return max(qry2(l, m, k * 2, a, b, c, d), qry2(m + 1, r, k * 2 + 1, a, b, c, d));
}

void upd1(int l, int r, int k, int ind, int x, int val) {
    if (r < x || x < l)
        return;
    if (x <= l && r <= x) {
        tree[ind][k] = val;
        return;
    }
    int m = (l + r) / 2;
    if (m >= x)
        upd1(l, m, k * 2, ind, x, val);
    if (m + 1 <= x)
        upd1(m + 1, r, k * 2 + 1, ind, x, val);
    tree[ind][k] = max(tree[ind][k * 2], tree[ind][k * 2 + 1]);
}

void upd2(int l, int r, int k, int x, int y, int val) {
    if (r < x || x < l)
        return;
    if (x <= l && r <= x) {
        upd1(0, w - 1, 1, k, y, val);
        return;
    }
    int m = (l + r) / 2;
    if (m >= x)
        upd2(l, m, k * 2, x, y, val);
    if (m + 1 <= x)
        upd2(m + 1, r, k * 2 + 1, x, y, val);
    prop(0, w - 1, 1, k, y);
}

int ret = 0;

void give_initial_chart(int H, int W, std::vector<int> r, std::vector<int> c) {
    h = H, w = W;
    for (int i = 0; i < h * w; i++) {
        arr[r[i]][c[i]] = i;
        pos[i] = {r[i], c[i]};
    }
    build(0, h * w - 1, 1);
    if (max(h, w) <= 1000) {
        build2(0, h - 1, 1);
        int x1, y1, x2, y2;
        tie(x1, y1) = pos[0];
        tie(x2, y2) = pos[0];
        for (int i = 0; i < h * w; i++) {
            x1 = min(x1, pos[i].fi); y1 = min(y1, pos[i].se);
            x2 = max(x2, pos[i].fi); y2 = max(y2, pos[i].se);
            int val = qry2(0, h - 1, 1, x1, x2, y1, y2);
            array<int,4> z = qry(0, h * w - 1, 1, val);
            x1 = z[0], y1 = z[1], x2 = z[2], y2 = z[3];
            i = val;
            if ((y2 - y1 + 1) * (x2 - x1 + 1) == val + 1)
                ret++;
        }
    } else {
        int x1, y1, x2, y2;
        tie(x1, y1) = pos[0];
        tie(x2, y2) = pos[0];
        for (int i = 0; i < h * w; i++) {
            x1 = min(x1, pos[i].fi); y1 = min(y1, pos[i].se);
            x2 = max(x2, pos[i].fi); y2 = max(y2, pos[i].se);
            if ((y2 - y1 + 1) * (x2 - x1 + 1) == i + 1)
                ret++;
        }
    }
}

int brute(int a, int b) {
    int cnt = 0;
    int x1, y1, x2, y2;
    array<int,4> z = qry(0, h * w - 1, 1, a);
    x1 = z[0], y1 = z[1], x2 = z[2], y2 = z[3];
    for (int i = a; i <= b; i++) {
        x1 = min(x1, pos[i].fi); y1 = min(y1, pos[i].se);
        x2 = max(x2, pos[i].fi); y2 = max(y2, pos[i].se);
        if ((y2 - y1 + 1) * (x2 - x1 + 1) == i + 1)
            cnt--;
    }
    swap(pos[a], pos[b]);
    upd(0, h * w - 1, 1, a);
    upd(0, h * w - 1, 1, b);
    z = qry(0, h * w - 1, 1, a);
    x1 = z[0], y1 = z[1], x2 = z[2], y2 = z[3];
    for (int i = a; i <= b; i++) {
        x1 = min(x1, pos[i].fi); y1 = min(y1, pos[i].se);
        x2 = max(x2, pos[i].fi); y2 = max(y2, pos[i].se);
        if ((y2 - y1 + 1) * (x2 - x1 + 1) == i + 1)
            cnt++;
    }
    ret += cnt;
    return ret;
}

int swap_seats(int a, int b) {
    if (a > b)
        swap(a, b);
    if (max(h, w) > 1000)
        return brute(a, b);
    int cnt = 0;
    int x1, y1, x2, y2;
    array<int,4> z = qry(0, h * w - 1, 1, a);
    x1 = z[0], y1 = z[1], x2 = z[2], y2 = z[3];
    for (int i = a; i <= b; i++) {
        x1 = min(x1, pos[i].fi); y1 = min(y1, pos[i].se);
        x2 = max(x2, pos[i].fi); y2 = max(y2, pos[i].se);
        int val = qry2(0, h - 1, 1, x1, x2, y1, y2);
        if (val > b)
            break;
        z = qry(0, h * w - 1, 1, val);
        x1 = z[0], y1 = z[1], x2 = z[2], y2 = z[3];
        i = val;
        if ((y2 - y1 + 1) * (x2 - x1 + 1) == val + 1)
            cnt--;
    }
    upd2(0, h - 1, 1, pos[a].fi, pos[a].se, b);
    upd2(0, h - 1, 1, pos[b].fi, pos[b].se, a);
    swap(pos[a], pos[b]);
    upd(0, h * w - 1, 1, a);
    upd(0, h * w - 1, 1, b);
    z = qry(0, h * w - 1, 1, a);
    x1 = z[0], y1 = z[1], x2 = z[2], y2 = z[3];
    for (int i = a; i <= b; i++) {
        x1 = min(x1, pos[i].fi); y1 = min(y1, pos[i].se);
        x2 = max(x2, pos[i].fi); y2 = max(y2, pos[i].se);
        int val = qry2(0, h - 1, 1, x1, x2, y1, y2);
        if (val > b)
            break;
        z = qry(0, h * w - 1, 1, val);
        x1 = z[0], y1 = z[1], x2 = z[2], y2 = z[3];
        i = val;
        if ((y2 - y1 + 1) * (x2 - x1 + 1) == val + 1)
            cnt++;
    }
    ret += cnt;
    return ret;
}

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