| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 278517 | ASDF123 | Seats (IOI18_seats) | C++14 | 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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define chkmax(a, b) a = max((a), (b))
#define chkmin(a, b) a = min((a), (b))
#define szof(s) (int)s.size()
#define pii pair<int, int>
#define fr first
#define sc second
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 5;
int r[N], c[N];
int ourH, ourW;
ordered_set row[N], col[N];
int S;
void go(bool ok) {
if (!ok) {
while (1) {
}
}
}
struct node {
int mn, mx;
node() {
mn = INF;
mx = -INF;
}
};
struct strange {
};
struct Tree {
vector <node> tree;
Tree() {
tree.resize(N * 4);
}
void upd(int pos, int val, int v = 1, int tl = 1, int tr = N) {
if (tl == tr) {
tree[v].mn = tree[v].mx = val;
return;
}
int mid = tl + tr >> 1;
if (pos <= mid) {
upd(pos, val, v + v, tl, mid);
}
else {
upd(pos, val, v + v + 1, mid + 1, tr);
}
tree[v].mn = min(tree[v + v].mn, tree[v + v + 1].mn);
tree[v].mx = max(tree[v + v].mx, tree[v + v + 1].mx);
}
pii merge(pii a, pii b) {
return { min(a.fr, b.fr), max(a.sc, b.sc) };
}
pii getpair(int l, int r, int v = 1, int tl = 1, int tr = N) {
if (l <= tl && tr <= r) {
return { tree[v].mn, tree[v].mx };
}
if (l > tr || tl > r) {
return { INF, -INF };
}
int mid = tl + tr >> 1;
return merge(getpair(l, r, v + v, tl, mid), getpair(l, r, v + v + 1, mid + 1, tr));
}
int get(int l, int r, int type, int v = 1, int tl = 1, int tr = N) {
if (l <= tl && tr <= r) {
if (type == 1) {
return tree[v].mn;
}
else {
return tree[v].mx;
}
}
if (l > tr || tl > r) {
if (type == 1) {
return INF;
}
else {
return -INF;
}
}
int mid = tl + tr >> 1;
int lft = get(l, r, type, v + v, tl, mid);
int rgt = get(l, r, type, v + v + 1, mid + 1, tr);
if (type == 1) {
return min(lft, rgt);
}
else {
return max(lft, rgt);
}
}
} rows, columns;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
for (int i = 0; i < H * W; i++) {
r[i + 1] = R[i] + 1;
c[i + 1] = C[i] + 1;
}
ourH = H;
ourW = W;
for (int i = 1; i <= ourH * ourW; i++) {
rows.upd(i, r[i]);
columns.upd(i, c[i]);
}
for (int i = 1; i <= ourH * ourW; i++) {
row[r[i]].insert(i);
col[c[i]].insert(i);
}
}
bool f = false;
int subtask12(int a, int b) {
int ans = 0;
a++, b++;
swap(r[a], r[b]);
swap(c[a], c[b]);
node R, C;
for (int i = 1; i <= ourH * ourW; i++) {
chkmin(R.mn, r[i]);
chkmax(R.mx, r[i]);
chkmin(C.mn, c[i]);
chkmax(C.mx, c[i]);
if ((R.mx - R.mn + 1) * (C.mx - C.mn + 1) == i) {
ans++;
}
}
return ans;
}
void go(pii &a) {
go(a.fr >= 1 && a.fr <= S);
go(a.sc >= 1 && a.sc <= S);
}
int square(int pos) {
go(pos >= 1 && pos <= S);
pii a = rows.getpair(1, pos);
pii b = columns.getpair(1, pos);
go(a);
go(b);
return (a.sc - a.fr + 1) * (b.sc - b.fr + 1);
}
int get(int pos) {
int s = square(pos);
pii a = rows.getpair(1, s);
pii b = columns.getpair(1, s);
int ss = square(s);
go(a);
go(b);
return ss == s ? ss : -1;
}
int subtask3(int a, int b) {
// if a b is 0 index
a++, b++;
go(1 <= r[a] && r[a] <= S);
go(1 <= c[a] && c[a] <= S);
go(1 <= r[b] && r[b] <= S);
go(1 <= c[b] && c[b] <= S);
row[r[a]].erase(a);
col[c[a]].erase(a);
row[r[b]].erase(b);
col[c[b]].erase(b);
swap(r[a], r[b]);
swap(c[a], c[b]);
row[r[a]].insert(a);
col[c[a]].insert(a);
row[r[b]].insert(b);
col[c[b]].insert(b);
rows.upd(a, r[a]);
columns.upd(a, c[a]);
rows.upd(b, r[b]);
columns.upd(b, c[b]);
set <int> used = { -1 };
for (int i = 1; i <= ourH; i++) {
go(!row[i].empty());
int best = *row[i].begin();
used.insert(get(best));
}
for (int i = 1; i <= ourW; i++) {
go(!col[i].empty());
int best = *col[i].begin();
used.insert(get(best));
}
return szof(used) - 1; // without -1
}
int swap_seats(int a, int b) { // answer after swap
/*if (ourH * ourW <= 10000) {
return subtask12(a, b);
}*/
if (ourH <= 1000 && ourW <= 1000) {
return subtask3(a, b);
}
assert(false);
}