| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 98608 | 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.
//#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;
}*/