| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1020298 | otarius | Best Place (NOI17_bestplace) | 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>
using namespace std;
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair <int, int>
#define ull unsigned long long
// #define int long long
// #define int unsigned long long
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
const ll inf = 1e9 + 7;
const ll weirdMod = 998244353;
const int maxN = 5 * 1e5 + 25;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
pii rt[maxN];
bool used[maxN];
set<int> pos[maxN];
vector<int> g[maxN], vec;
ordered_set fen[maxN];
int n, r, c, q, par[maxN], sz[maxN], p[maxN][20], in[maxN], out[maxN], nxt[maxN], tim = 0;
int f(int i, int j) {
return (i - 1) * r + j;
}
int find_set(int x) {
if (par[x] == x) return x;
return par[x] = find_set(par[x]);
}
void union_set(int x, int y) {
x = find_set(x);
y = find_set(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
par[y] = x; sz[x] += sz[y];
rt[x] = max(rt[x], rt[y]);
}
void dfs(int v, int pr) {
vec.pb(v);
p[v][0] = pr;
in[v] = ++tim;
for (int u : g[v]) dfs(u, v);
out[v] = tim;
}
void update(int x, int val) {
for ( ; x <= n; x += (x & -x)) fen[x].insert({val, ++tim});
}
void erase(int x, int val) {
for ( ; x <= n; x += (x & -x)) fen[x].erase(fen[x].lower_bound({val, 0}));
}
int query(int x, int val) {
int ans = 0;
for ( ; x; x -= x & -x) {
ans += fen[x].size() - fen[x].order_of_key({val + 1, 0});
} return ans;
}
void solve() {
cin >> r >> c >> q;
n = r * c;
int val[n + 1];
vector<pair<int, pii>> ord;
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
cin >> val[f(i, j)]; ord.pb({val[f(i, j)], {i, j}});
}
} sort(ord.begin(), ord.end());
int clr[n + 1];
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++) cin >> clr[f(i, j)];
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
sz[f(i, j)] = 1;
par[f(i, j)] = f(i, j);
rt[f(i, j)] = {val[f(i, j)], f(i, j)};
}
} for (auto u : ord) {
pii cur = u.sc;
used[f(cur.ff, cur.sc)] = 1;
for (int i = 0; i < 4; i++) {
int x = cur.ff + dx[i];
int y = cur.sc + dy[i];
if (x > r || y > c || x < 1 || y < 1 || val[f(x, y)] > val[f(cur.ff, cur.sc)]) continue;
if (find_set(f(x, y)) == find_set(f(cur.ff, cur.sc))) continue;
g[rt[find_set(f(cur.ff, cur.sc))].sc].pb(rt[find_set(f(x, y))].sc);
union_set(f(cur.ff, cur.sc), f(x, y));
}
} dfs(f(ord.back().sc.ff, ord.back().sc.sc), f(ord.back().sc.ff, ord.back().sc.sc));
for (int j = 1; j < 20; j++)
for (int i = 1; i <= n; i++)
p[i][j] = p[p[i][j - 1]][j - 1];
tim = 0;
for (int i = 1; i < maxN; i++) pos[i].insert(maxN);
vec.insert(vec.begin(), 0);
for (int i = vec.size() - 1; i >= 1; i--)
nxt[i] = *pos[clr[vec[i]]].begin(), pos[clr[vec[i]]].insert(i);
for (int i = 1; i < vec.size() - 1; i++) update(i, nxt[i]);
while (q--) {
int t; cin >> t;
if (t == 1) {
int x, y, p;
cin >> x >> y >> p;
erase(in[f(x, y)], nxt[in[f(x, y)]]);
pos[clr[f(x, y)]].erase(in[f(x, y)]);
auto it = pos[clr[f(x, y)]].lower_bound(in[f(x, y)]);
if (it != pos[clr[f(x, y)]].begin()) {
it--; erase(*it, in[f(x, y)]);
nxt[*it] = *next(it);
update(*it, *next(it));
} clr[f(x, y)] = p;
it = pos[clr[f(x, y)]].lower_bound(in[f(x, y)]);
nxt[in[f(x, y)]] = *it;
update(in[f(x, y)], nxt[in[f(x, y)]]);
if (it != pos[clr[f(x, y)]].begin()) {
it--; erase(*it, *next(it));
nxt[*it] = in[f(x, y)];
update(*it, in[f(x, y)]);
} pos[clr[f(x, y)]].insert(in[f(x, y)]);
} else {
int x, y, l;
cin >> x >> y >> l;
int pos = f(x, y);
if (val[pos] > l) {
cout << "0\n"; continue;
} for (int i = 19; i >= 0; i--) {
if (val[p[pos][i]] <= l) pos = p[pos][i];
} cout << query(out[pos], out[pos]) - query(in[pos] - 1, out[pos]) << '\n';
}
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
cout << '\n';
}
return 0;
}