제출 #98607

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98607		eriksuenderhauf	자리 배치 (IOI18_seats)	C++11	컴파일 에러	0 ms	0 KiB

seats

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "seats.h"
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e3 + 5;
const double eps = 1e-9;
int tree[3 * MAXN][3 * MAXN];
int arr[MAXN][MAXN];
pii pos[MAXN * MAXN];
int h = 0, w = 0;

struct comp {
    int x1=INF, y1=INF, x2=-1, y2=-1;
} tree1d[3 * MAXN * MAXN];

void build(int l, int r, int k) {
    if (l == r) {
        //cerr << h << " " << w << " " << h * w - 1 << " " << k << "\n";
        tree1d[k].x1 = pos[l].fi;
        tree1d[k].y1 = pos[l].se;
        tree1d[k].x2 = pos[r].fi;
        tree1d[k].y2 = pos[r].se;
        return;
    }
    int m = (l + r) / 2;
    build(m + 1, r, k * 2 + 1);
    build(l, m, k * 2);
    tree1d[k].x1 = min(tree1d[k * 2].x1, tree1d[k * 2 + 1].x1);
    tree1d[k].y1 = min(tree1d[k * 2].y1, tree1d[k * 2 + 1].y1);
    tree1d[k].x2 = max(tree1d[k * 2].x2, tree1d[k * 2 + 1].x2);
    tree1d[k].y2 = max(tree1d[k * 2].y2, tree1d[k * 2 + 1].y2);
}

comp qry(int l, int r, int k, int a) {
    if (r < 0 || a < l) {
        comp ret;
        ret.x1 = INF;
        ret.y1 = INF;
        ret.x2 = -1;
        ret.y2 = -1;
        return ret;
    }
    if (0 <= l && r <= a)
        return tree1d[k];
    int m = (l + r) / 2;
    comp x = qry(l, m, k * 2, a);
    comp y = qry(m + 1, r, k * 2 + 1, a);
    x.x1 = min(x.x1, y.x1);
    x.y1 = min(x.y1, y.y1);
    x.x2 = max(x.x2, y.x2);
    x.y2 = max(x.y2, y.y2);
    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].x1 = pos[l].fi;
        tree1d[k].y1 = pos[l].se;
        tree1d[k].x2 = pos[r].fi;
        tree1d[k].y2 = pos[r].se;
        //tree1d[k] = {pos[l].fi, pos[l].se, pos[r].fi, pos[r].se};
        return;
    }
    int m = (l + r) / 2;
    upd(l, m, k * 2, a);
    upd(m + 1, r, k * 2 + 1, a);
    tree1d[k].x1 = min(tree1d[k * 2].x1, tree1d[k * 2 + 1].x1);
    tree1d[k].y1 = min(tree1d[k * 2].y1, tree1d[k * 2 + 1].y1);
    tree1d[k].x2 = max(tree1d[k * 2].x2, tree1d[k * 2 + 1].x2);
    tree1d[k].y2 = max(tree1d[k * 2].y2, tree1d[k * 2 + 1].y2);
}

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

void give_initial_chart(int H, int W, vi r, vi 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);
    build2(0, h - 1, 1);
}

int swap_seats(int a, int b) {
    //cerr << h << " " << w << " " << h * w - 1 << "\n";
    int ret = 0;
    int x1, y1, x2, y2;
    upd2(0, h - 1, 1, pos[a].se, pos[a].fi, b);
    upd2(0, h - 1, 1, pos[b].se, pos[b].fi, a);
    //comp xz = qry(0, h * w - 1, 1, 0);
    //cerr << xz.x1 << " " << xz.x2 << " " << xz.y1 << " " << xz.y2 << " " << pos[0].fi << " " << pos[0].se << "\n";
    swap(pos[a], pos[b]);
    upd(0, h * w - 1, 1, a);
    upd(0, h * w - 1, 1, b);
    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);
        //cerr << val << " " << x1 << " " << x2 << " " << y1 << " " << y2 << " ";
        comp z = qry(0, h * w - 1, 1, val);
        //cerr << val << " " << z.x1 << " " << z.x2 << " " << z.y1 << " " << z.y2 << "\n";
        x1 = z.x1, y1 = z.y1, x2 = z.x2, y2 = z.y2;
        /*while (i <= val) {
            x1 = min(x1, pos[i].fi); y1 = min(y1, pos[i].se);
            x2 = max(x2, pos[i].fi); y2 = max(y2, pos[i].se);
            i++;
        }*/
        i = val;
        if ((y2 - y1 + 1) * (x2 - x1 + 1) == val + 1)
            ret++;
    }
    //cerr << a << " " << b << " " << ret << "\n";
    return ret;
}

/*int main() {
    vi r = {2, 1, 0, 0, 0, 2, 1, 1, 2};
    vi c = {2, 2, 2, 1, 0, 1, 1, 0, 0};
    give_initial_chart(3, 3, r, c);
    swap_seats(6, 0);
    swap_seats(5, 7);
    swap_seats(6, 4);
    return 0;
}*/

컴파일 시 표준 에러 (stderr) 메시지

Compilation timeout while compiling seats