| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 999531 | cadmiumsky | Seats (IOI18_seats) | C++17 | 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 <bits/stdc++.h>
#include "seats.h"
#define all(x) (x).begin(),(x).end()
using namespace std;
using pii = pair<int,int>;
#define sz(x) ((int)(x).size())
template<typename Node>
struct AINT {
vector<Node> aint;
int n;
void init(int n_) {
n = n_;
aint.assign(2 * n + 5, Node());
}
template<class CB> void walk(CB&& cb) { walk(cb, 0, n); }
template<class CB> void walk(CB&& cb, int l, int r) { walk(cb, l, r, 1, 0, n); }
template<class CB> void walk(CB&& cb, int l, int r, int node, int cl, int cr) {
if(cr < l || r < cl) return;
if(l <= cl && cr <= r && !cb(aint[node], cl, cr)) return;
int mid = (cl + cr) >> 1, L = node + 1, R = node + (mid - cl + 1) * 2;
aint[node].push(aint[L], aint[R]);
walk(cb, l, r, L, cl, mid);
walk(cb, l, r, R, mid + 1, cr);
aint[node].pull(aint[L], aint[R]);
}
};
const int necesar = 1;
struct nmns : pii {
void pull(const nmns& L, const nmns& R) {
first = min(L.first, R.first);
second = (L.first == first) * L.second + (R.first == first) * R.second;
}
void apply(int x) { first += x; }
};
struct Node {
nmns val;
int lazy;
void push(Node& L, Node& R) {
if(lazy == 0) return;
L.val.apply(lazy);
R.val.apply(lazy);
L.lazy += lazy;
R.lazy += lazy;
lazy = 0;
}
void pull(const Node& L, const Node& R) {
val.pull(L.val, R.val);
}
};
AINT<Node> aint;
void add(int l, int r, int val) {
aint.walk([&](Node& node, int cl, int cr) { node.val.apply(val); node.lazy += val; return 0;}, l, r);
}
int query() {
//aint.walk([&](Node& node, int cl, int cr) { cerr << "--\n"; for(auto [a, b] : node.val) cerr << '\t' << a << ": " << b << '\n'; cerr << "--\n"; return 0;}, 2, 2);
auto v = aint.aint[1].val;
//aint.walk([&](Node& val, int cl, int cr) {
//if(cl != cr) return 1;
//cerr << val.val[0].first << ": " << val.val[0].second << ",\t";
//return 0;
//});
//cerr << '\n';
return v.second;
}
vector<vector<int>> mat;
vector<int> R, C;
int H, W;
vector<vector<int>> added;
void modcorner(int i, int j, int aggr) {
if(added[i][j] == aggr) return;
added[i][j] = aggr;
vector<int> val;
val.emplace_back(mat[i][j]);
val.emplace_back(mat[i + 1][j]);
val.emplace_back(mat[i + 1][j + 1]);
val.emplace_back(mat[i][j + 1]);
sort(all(val));
add(val[0], val[1] - 1, aggr);
add(val[2], val[3] - 1, aggr);
return;
}
void modcell(int i, int j, int aggr) {
for(int a = -1; a <= 1; a++)
for(int b = -1; b <= 1; b++)
if(i + a >= 0 && i + a <= H && j + b >= 0 && j + b <= W)
modcorner(i + a, j + b, aggr);
}
void give_initial_chart(int H_, int W_, std::vector<int> R_, std::vector<int> C_) {
H = H_; W = W_; R = R_; C = C_;
mat.assign(H + 2, vector<int>(W + 2, H * W + 1));
added.assign(H + 2, vector<int>(W + 2, 0));
for(auto &x : R) x++;
for(auto &x : C) x++;
for(int i = 0; i < H * W; i++) mat[R[i]][C[i]] = i;
aint.init(H * W - 1);
aint.walk([&](Node& val, int cl, int cr) {
if(cl != cr) return 1;
val.val = make_pair(0, 1);
return 0;
});
for(int i = 0; i <= H; i++)
for(int j = 0; j <= W; j++)
modcorner(i, j, 1);
}
int swap_seats(int a, int b) {
auto [x, y] = make_pair(R[a], C[a]);
auto [u, v] = make_pair(R[b], C[b]);
swap(R[a], R[b]);
swap(C[a], C[b]);
modcell(x, y, -1);
modcell(u, v, -1);
swap(mat[x][y], mat[u][v]);
modcell(x, y, 1);
modcell(u, v, 1);
return query();
}