| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 98609 | eriksuenderhauf | Seats (IOI18_seats) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
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) {
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;
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, 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);
build2(0, h - 1, 1);
}
int swap_seats(int a, int b) {
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);
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);
comp z = qry(0, h * w - 1, 1, val);
x1 = z.x1, y1 = z.y1, x2 = z.x2, y2 = z.y2;
i = val;
if ((y2 - y1 + 1) * (x2 - x1 + 1) == val + 1)
ret++;
}
return ret;
}