#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
#define file ""
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define popcount __builtin_popcountll
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return l + rd() % (r - l + 1);
}
const int N = 1e6 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;
template<class X, class Y> bool mini(X &a, Y b) {
return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int m, n, q;
vector<vector<int> > a;
namespace task1 {
bool check() {
return m * n <= 10000 && q <= 10000;
}
bool inside(int x, int y) {
return 1 <= x && x <= m && 1 <= y && y <= n;
}
void Paint(int Ax, int Ay, int NewColor) {
vector<vector<int> > vis(m + 5, vector<int> (n + 5, 0));
queue<pair<int,int> > Q;
Q.push({Ax, Ay});
vis[Ax][Ay] = true;
int FirstColor = a[Ax][Ay];
a[Ax][Ay] = NewColor;
while (Q.size()) {
int x, y;
tie(x, y) = Q.front(); Q.pop();
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k];
int ny = y + dy[k];
if (!vis[nx][ny] && inside(nx, ny) && a[nx][ny] == FirstColor) {
a[nx][ny] = NewColor;
vis[nx][ny] = true;
Q.push({nx, ny});
}
}
}
}
void solve() {
while (q--) {
int x, y, NewColor;
cin >> x >> y >> NewColor;
Paint(x, y, NewColor);
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) cout << a[i][j] << ' ';
cout << '\n';
}
}
}
namespace task2 {
bool check() {
return m == 1;
}
struct SegMax {
vector<int> maxval, lazy, rec;
int n;
void init(int _n) {
n = _n;
maxval.assign(n * 4 + 5, 0);
lazy.assign(n * 4 + 5, 0);
rec.assign(n * 4 + 5, 0);
}
void down(int i) {
if (!rec[i])
return;
for (int j = i * 2; j <= i * 2 + 1; ++j) maxval[j] = lazy[j] = lazy[i], rec[j] = true;
rec[i] = false;
}
void update(int i, int L, int R, int l, int r, int c) {
if (r < L || l > R)
return;
if (l <= L && R <= r) {
maxval[i] = c;
lazy[i] = c;
rec[i] = true;
return;
}
down(i);
int M = (L + R) >> 1;
update(i << 1, L, M, l, r, c);
update(i << 1 | 1, M + 1, R, l, r, c);
maxval[i] = max(maxval[i << 1], maxval[i << 1 | 1]);
}
int get(int i, int L, int R, int l, int r) {
if (r < L || l > R)
return -oo;
if (l <= L && R <= r)
return maxval[i];
down(i);
int M = (L + R) >> 1;
return max(get(i << 1, L, M, l, r), get(i << 1 | 1, M + 1, R, l, r));
}
void update(int l, int r, int c) {
update(1, 1, n, l, r, c);
}
int get(int l, int r) {
return get(1, 1, n, l, r);
}
} Tmax;
struct SegMin {
vector<int> minval, lazy, rec;
int n;
void init(int _n) {
n = _n;
minval.assign(n * 4 + 5, 0);
lazy.assign(n * 4 + 5, 0);
rec.assign(n * 4 + 5, 0);
}
void down(int i) {
if (!rec[i])
return;
for (int j = i * 2; j <= i * 2 + 1; ++j) minval[j] = lazy[j] = lazy[i], rec[j] = true;
rec[i] = false;
}
void update(int i, int L, int R, int l, int r, int c) {
if (r < L || l > R)
return;
if (l <= L && R <= r) {
minval[i] = c;
lazy[i] = c;
rec[i] = true;
return;
}
down(i);
int M = (L + R) >> 1;
update(i << 1, L, M, l, r, c);
update(i << 1 | 1, M + 1, R, l, r, c);
minval[i] = min(minval[i << 1], minval[i << 1 | 1]);
}
int get(int i, int L, int R, int l, int r) {
if (r < L || l > R)
return oo;
if (l <= L && R <= r)
return minval[i];
down(i);
int M = (L + R) >> 1;
return min(get(i << 1, L, M, l, r), get(i << 1 | 1, M + 1, R, l, r));
}
void update(int l, int r, int c) {
update(1, 1, n, l, r, c);
}
int get(int l, int r) {
return get(1, 1, n, l, r);
}
} Tmin;
void solve() {
Tmax.init(n);
Tmin.init(n);
for (int i = 1; i <= n; ++i) {
Tmax.update(i, i, a[1][i]);
Tmin.update(i, i, a[1][i]);
}
while (q--) {
int x, NewColor;
cin >> x >> x >> NewColor;
int lpos, rpos;
int l = 1, r = x;
int res = x;
while (l <= r) {
int mid = (l + r) / 2;
int curmax = Tmax.get(mid, x);
int curmin = Tmin.get(mid, x);
if (curmax == curmin) {
res = mid;
r = mid - 1;
} else l = mid + 1;
}
lpos = res;
l = x, r = n;
res = x;
while (l <= r) {
int mid = (l + r) / 2;
int curmax = Tmax.get(x, mid);
int curmin = Tmin.get(x, mid);
if (curmax == curmin) {
res = mid;
l = mid + 1;
} else r = mid - 1;
}
rpos = res;
Tmax.update(lpos, rpos, NewColor);
Tmin.update(lpos, rpos, NewColor);
}
for (int i = 1; i <= n; ++i) cout << Tmax.get(i, i) << ' ';
}
}
void process() {
cin >> m >> n;
a.resize(m + 5, vector<int>(n + 5, 0));
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j) cin >> a[i][j];
cin >> q;
if (task1::check()) {task1::solve(); return;}
if (task2::check()) {task2::solve(); return;}
// task1::solve();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#else
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
#endif
int tc = 1;
// cin >> tc;
while (tc--) {
process();
}
return 0;
}
/*
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
10 ms |
592 KB |
Output is correct |
| 4 |
Correct |
26 ms |
544 KB |
Output is correct |
| 5 |
Correct |
353 ms |
540 KB |
Output is correct |
| 6 |
Correct |
466 ms |
536 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1113 ms |
6596 KB |
Output is correct |
| 2 |
Correct |
1302 ms |
13380 KB |
Output is correct |
| 3 |
Correct |
1739 ms |
27152 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
