// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
#define f first
#define s second
#define mp make_pair
template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using vpi = V<pi>;
int dx[4] = { 0, 0, -1, +1};
int dy[4] = {-1, +1, 0, 0};
const int SQ = 630; // determines what is heavy and what is light
struct Scanner {
FILE* stream;
Scanner(FILE* s) : stream(s) {}
char buf[1 << 20], * l = buf, * r = buf;
bool flush() { l = buf; r = l + fread(buf, 1, 1 << 20, stream); return l == r; }
void get(char& c) { c = l == r && flush() ? ' ' : *l++; }
friend Scanner& operator >>(Scanner& in, char& c) { return in.get(c), in; }
friend Scanner& operator >>(Scanner& in, char* s) {
for (in.get(s[0]); isspace(s[0]); in.get(s[0]));
for (int i = 0; !isspace(s[i]) || (s[i] = '\0'); i++) in.get(s[i + 1]);
return in;
}
friend Scanner& operator >>(Scanner& in, std::string& s) {
char c;
for (in.get(c); isspace(c); in.get(c));
for (s = ""; !isspace(c); in.get(c)) s += c;
return in;
}
template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
friend Scanner& operator >>(Scanner& in, T& x) {
char c, f = '+';
for (in.get(c); !isdigit(c); in.get(c))
if constexpr (std::is_signed_v<T>) f = c;
for (x = 0; isdigit(c); in.get(c)) x = x * (1 << 1) + x * (1 << 3) + c - '0';
if constexpr (std::is_signed_v<T>) x = f == '-' ? -x : x;
return in;
}
template <class T, std::enable_if_t<std::is_floating_point_v<T>, int> = 0>
friend Scanner& operator >>(Scanner& in, T& x) {
std::string s; in >> s; x = std::stod(s);
return in;
}
template <class T, class U>
friend Scanner& operator >>(Scanner& in, std::pair<T, U>& a) {
return in >> a.first >> a.second;
}
template <class T, size_t S>
friend Scanner& operator >>(Scanner& in, std::array<T, S>& a) {
for (int i = 0, n = S; i < n; i++) in >> a[i];
return in;
}
template <class T>
friend Scanner& operator >>(Scanner& in, std::vector<T>& a) {
for (int i = 0, n = a.size(); i < n; i++) in >> a[i];
return in;
}
};
struct Printer {
FILE* stream;
Printer(FILE* s) : stream(s) {}
char buf[1 << 20], * l = buf, * r = buf + (1 << 20) - 1;
int format = 0, precision = 15;
~Printer() { flush(); }
void flush() { fwrite(buf, 1, l - buf, stream); l = buf; }
void put(const char& c) { *l++ = c; if (l == r) flush(); }
friend Printer& operator <<(Printer& out, const char& c) { return out.put(c), out; }
friend Printer& operator <<(Printer& out, const char* s) {
for (int i = 0; s[i] != '\0'; i++) out.put(s[i]);
return out;
}
friend Printer& operator <<(Printer& out, const std::string& s) {
for (int i = 0, n = s.size(); i < n; i++) out.put(s[i]);
return out;
}
template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
friend Printer& operator <<(Printer& out, T x) {
static char s[40];
static int i = 0;
if (x == 0) { out.put('0'); return out; }
if constexpr (std::is_signed_v<T>) x = x < 0 ? out.put('-'), -x : x;
while (x > 0) s[++i] = x % 10 + '0', x /= 10;
while (i > 0) out.put(s[i--]);
return out;
}
template <class T, std::enable_if_t<std::is_floating_point_v<T>, int> = 0>
friend Printer& operator <<(Printer& out, T x) {
std::ostringstream oss;
oss << std::fixed << std::setprecision(out.precision) << x;
return out << oss.str();
}
template <class T, class U>
friend Printer& operator <<(Printer& out, const std::pair<T, U>& a) {
return out << a.first << " \n"[out.format > 1] << a.second;
}
template <class T, size_t S>
friend Printer& operator <<(Printer& out, const std::array<T, S>& a) {
out << a[0];
for (int i = 1, n = S; i < n; i++) out << " \n"[out.format > 1] << a[i];
return out;
}
template <class T>
friend Printer& operator <<(Printer& out, const std::vector<T>& a) {
if (!a.empty()) out << a[0];
for (int i = 1, n = a.size(); i < n; i++) out << " \n"[out.format > 0] << a[i];
return out;
}
};
Scanner in(stdin);
Printer out(stdout);
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, M; in >> N >> M;
// auto P = [&](int x) {
// return "{ " + to_string(x / M) + " " + to_string(x % M) + " }";
// };
V<vi> A(N, vi(M)); for(int r = 0; r < N; r++) for(int c = 0; c < M; c++) {
in >> A[r][c];
}
vi ID(N * M), C(N * M), H(N * M, 0); V<vi> E(N * M); V<set<int>> EH(N * M); V<set<pi>> L(N * M);
// L -> adj to the set (color, vertex)
vpi CMB;
for(int r = 0; r < N; r++) for(int c = 0; c < M; c++) {
ID[r * M + c] = r * M + c;
for(int d = 0; d < 4; d++) {
int nr = r + dx[d], nc = c + dy[d];
if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
E[r * M + c].pb(nr * M + nc); // add edge between adj. cells
if (A[r][c] == A[nr][nc]) CMB.pb(mp(r * M + c, nr * M + nc));
}
C[r * M + c] = A[r][c];
}
function<int(int)> get = [&](int u) {
return ID[u] == u ? u : ID[u] = get(ID[u]);
};
auto merge = [&](int u, int v) {
// cout << u / M << " " << u % M << " <= U => " << v / M << " " << v % M << endl;
u = get(u), v = get(v);
if (u == v) return;
if (sz(E[u]) < sz(E[v])) swap(u, v);
if (sz(EH[u]) < sz(EH[v])) EH[u].swap(EH[v]);
if (sz(L[u]) < sz(L[v])) L[u].swap(L[v]);
for(auto x : E[v]) {
x = get(x);
if (H[x]) { // is hvy
// L[x].erase(mp(C[v], v));
if (H[u]) {
EH[x].insert(u);
EH[u].insert(x);
} else L[x].insert(mp(C[u], u));
} else { // is light
if (H[u]) L[u].insert(mp(C[x], x));
}
E[u].pb(x);
}
for(auto& x : EH[v]) EH[u].insert(get(x));
for(auto& x : L[v]) L[u].insert(x);
ID[v] = u;
if (!H[u] && sz(E[u]) > SQ) {
H[u] = 1;
for(auto x : E[u]) {
int r = get(x);
if (r == u) continue;
L[u].insert(mp(C[r], r));
if (H[r]) { // is hvy => hvy together
EH[r].insert(u);
EH[u].insert(r);
}
}
}
};
auto print = [&]() {
for(int r = 0; r < N; r++) {
for(int c = 0; c < M; c++) {
int u = r * M + c; out << C[get(u)] << " ";
}
out << nl;
}
};
for(auto& p : CMB) {
auto [u, v] = p;
merge(u, v);
}
// for(int r = 0; r < N; r++) {
// cout << "--------------------------------" << nl;
// for(int c = 0; c < M; c++) {
// int u = r * M + c; cout << P(get(u)) << " | ";
// }
// cout << nl;
// }
int Q; in >> Q;
for(int i = 0; i < Q; i++) {
int r, c, s; in >> r >> c >> s; --r, --c;
// if (i % 100 == 0) cout << i << endl;
int u = r * M + c; u = get(u);
// s stores the old color
swap(C[u], s);
vi cmb;
if (H[u]) { // if heavy:
// go through heavy nodes -> N / B
for(auto& v : EH[u]) {
int rx = get(v);
// cout << P(u) << " <= HH => " << P(rx) << nl;
if (rx != u && C[rx] == C[u]) cmb.pb(rx);
}
// go through light nodes -> log(N)
{
while(1) {
auto it = L[u].lower_bound(mp(C[u], -1));
if (it == end(L[u])) break;
auto [cv, v] = *it;
v = get(v);
if (cv == C[u]) {
if (C[v] == C[u]) cmb.pb(v);
L[u].erase(it);
} else break;
}
}
} else { // if light:
// go through all adjacent -> B * log(N)
for(auto& v : E[u]) {
int rx = get(v);
if (rx != u && C[rx] == C[u]) cmb.pb(rx);
if (H[rx]) { // is hvy
// L[rx].erase(mp(s, u));
L[rx].insert(mp(C[u], u));
}
}
}
for(auto& x : cmb) merge(u, x);
// print();
}
// after updates find the adjacents with the same color
// two parts -> color and adjacent
// can store either color or adjacent
// how do you check whether adjacent with a color?
// with adjacent you have to find color efficiently
// if you store (color, vertex) pair in a set, then you can find the adjacents quickly
// you also have to update them
// SQRT Decomp? but its N * sqrt(N) * log(N)?
// Light -> B * log(N) + (N / B), heavy -> N / B + log(N)
print();
exit(0-0);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2080 KB |
Output is correct |
| 5 |
Correct |
8 ms |
2908 KB |
Output is correct |
| 6 |
Correct |
10 ms |
3160 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
10136 KB |
Output is correct |
| 2 |
Correct |
84 ms |
22444 KB |
Output is correct |
| 3 |
Correct |
89 ms |
42856 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
101 ms |
41640 KB |
Output is correct |
| 2 |
Correct |
105 ms |
39232 KB |
Output is correct |
| 3 |
Correct |
132 ms |
41552 KB |
Output is correct |
| 4 |
Correct |
138 ms |
43136 KB |
Output is correct |
| 5 |
Correct |
107 ms |
40976 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
88 ms |
30216 KB |
Output is correct |
| 2 |
Correct |
280 ms |
53736 KB |
Output is correct |
| 3 |
Correct |
460 ms |
63332 KB |
Output is correct |
| 4 |
Correct |
314 ms |
57504 KB |
Output is correct |
| 5 |
Correct |
248 ms |
43516 KB |
Output is correct |
| 6 |
Correct |
99 ms |
41104 KB |
Output is correct |
| 7 |
Correct |
118 ms |
44868 KB |
Output is correct |
| 8 |
Correct |
117 ms |
45940 KB |
Output is correct |
| 9 |
Correct |
352 ms |
49028 KB |
Output is correct |
