#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 50004;
const int xx[4] = {0, 1, 0, -1};
const int yy[4] = {1, 0, -1, 0};
int n, m, q;
int** a;
int p0[N];
int fi(int x)
{
if (x == p0[x])
return x;
return p0[x] = fi(p0[x]);
}
void kpc(int x, int y)
{
x = fi(x);
y = fi(y);
p0[x] = y;
}
int uu(int x, int y)
{
return (x - 1) * m + y;
}
vector<int> g[N];
const int k = 18;
int p[N][k];
int tin[N], tout[N], ti;
void dfs0(int x, int p0)
{
tin[x] = ++ti;
p[x][0] = p0;
for (int i = 1; i < k; ++i)
p[x][i] = p[p[x][i - 1]][i - 1];
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i];
dfs0(h, x);
}
tout[x] = ti;
}
bool isp(int x, int y)
{
return (tin[x] <= tin[y] && tout[y] <= tout[x]);
}
int go(int x, int y)
{
for (int i = k - 1; i >= 0; --i)
{
int xx = p[x][i];
int ux = (xx - 1) / m + 1;
int uy = xx - (ux - 1) * m;
if (a[ux][uy] <= y)
x = xx;
}
return x;
}
int yyz;
int yyr[N * k * 5];
struct ban
{
int x, y;
ban *l, *r;
int q;
ban(){}
ban(int x)
{
this->x = x;
y = yyr[yyz++];
l = r = 0;
q = 1;
}
};
typedef ban* pban;
namespace treap
{
int getq(pban t)
{
if (t == 0)
return 0;
return t->q;
}
void ubd(pban t)
{
if (t == 0)
return;
t->q = getq(t->l) + 1 + getq(t->r);
}
void mer(pban l, pban r, pban& t)
{
if (l == 0)
{
t = r;
return;
}
if (r == 0)
{
t = l;
return;
}
if (l->y > r->y)
{
mer(l->r, r, l->r);
t = l;
}
else
{
mer(l, r->l, r->l);
t = r;
}
ubd(t);
}
void spl(pban t, int x, pban& l, pban& r)
{
if (t == 0)
{
l = r = 0;
return;
}
if (x < t->x)
{
spl(t->l, x, l, t->l);
r = t;
}
else
{
spl(t->r, x, t->r, r);
l = t;
}
ubd(l);
ubd(r);
}
void ave(pban& t, int x)
{
pban l, r;
spl(t, x, l, r);
pban m = new ban(x);
mer(l, m, t);
mer(t, r, t);
}
void han(pban& t, int x)
{
pban l, m, r;
spl(t, x, m, r);
spl(m, x - 1, l, m);
mer(l, r, t);
}
int ph(pban t, int x)
{
pban l, r;
spl(t, x, l, r);
int ans = getq(l);
mer(l, r, t);
return ans;
}
};
pban t[N * 4];
void ubd(int tl, int tr, int x, int y, bool z, int pos)
{
if (!z)
treap::han(t[pos], y);
else
treap::ave(t[pos], y);
if (tl == tr)
return;
int m = (tl + tr) / 2;
if (x <= m)
ubd(tl, m, x, y, z, pos * 2);
else
ubd(m + 1, tr, x, y, z, pos * 2 + 1);
}
int qry(int tl, int tr, int l, int r, int x, int pos)
{
if (l > r)
return 0;
if (tl == l && tr == r)
{
return treap::ph(t[pos], x);
}
int m = (tl + tr) / 2;
return (qry(tl, m, l, min(m, r), x, pos * 2) +
qry(m + 1, tr, max(m + 1, l), r, x, pos * 2 + 1));
}
set<int> s[N];
void ave(int i, int x)
{
s[i].insert(x);
auto it = s[i].find(x);
--it;
int hl = *it;
++it;
++it;
if (it != s[i].end())
{
ubd(1, n * m, *it, hl, false, 1);
ubd(1, n * m, *it, x, true, 1);
}
ubd(1, n * m, x, hl, true, 1);
}
void han(int i, int x)
{
auto it = s[i].find(x);
--it;
int hl = *it;
++it;
++it;
if (it != s[i].end())
{
ubd(1, n * m, *it, x, false, 1);
ubd(1, n * m, *it, hl, true, 1);
}
ubd(1, n * m, x, hl, false, 1);
s[i].erase(x);
}
int b[N];
void solv()
{
scanf("%d%d%d", &n, &m, &q);
a = new int*[n + 5];
for (int i = 0; i < n + 5; ++i)
{
a[i] = new int[m + 5];
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
scanf("%d", &a[i][j]);
}
}
vector<pair<int, pair<int, int> > > v;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
v.push_back(m_p(a[i][j], m_p(i, j)));
}
}
sort(all(v));
for (int i = 1; i <= n * m; ++i)
p0[i] = i;
for (int i = 0; i < n * m; ++i)
{
int x = v[i].se.fi;
int y = v[i].se.se;
for (int i = 0; i < 4; ++i)
{
int hx = x + xx[i];
int hy = y + yy[i];
if (!(hx >= 1 && hx <= n && hy >= 1 && hy <= m))
continue;
if (a[hx][hy] > a[x][y])
continue;
if (fi(uu(x, y)) != fi(uu(hx, hy)))
{
g[uu(x, y)].push_back(fi(uu(hx, hy)));
kpc(uu(hx, hy), uu(x, y));
}
}
}
dfs0(uu(v.back().se.fi, v.back().se.se), uu(v.back().se.fi, v.back().se.se));
for (int i = 1; i < N; ++i)
{
s[i].insert(-i);
}
for (int x = 1; x <= n * m; ++x)
{
scanf("%d", &b[x]);
ave(b[x], tin[x]);
}
while (q--)
{
int ty;
scanf("%d", &ty);
if (ty == 1)
{
int x, y, p;
scanf("%d%d%d", &y, &x, &p);
x = uu(x, y);
han(b[x], tin[x]);
b[x] = p;
ave(b[x], tin[x]);
}
else
{
int x, y, l;
scanf("%d%d%d", &y, &x, &l);
if (a[x][y] > l)
{
printf("0\n");
continue;
}
x = uu(x, y);
x = go(x, l);
printf("%d\n", qry(1, n * m, tin[x], tout[x], tin[x] - 1, 1));
}
}
}
int main()
{
#ifdef SOMETHING
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif // SOMETHING
//ios_base::sync_with_stdio(false), cin.tie(0);
for (int i = 0; i < N * k * 5; ++i)
{
yyr[i] = i;
}
for (int i = N * k * 5 - 1; i >= 0; --i)
{
swap(yyr[i], yyr[rnd() % (i + 1)]);
}
solv();
return 0;
}
//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}
Compilation message
pokemonmaster.cpp: In function 'void dfs0(int, int)':
pokemonmaster.cpp:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[x].size(); ++i)
~~^~~~~~~~~~~~~
pokemonmaster.cpp: In function 'void solv()':
pokemonmaster.cpp:253:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &m, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
pokemonmaster.cpp:263:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i][j]);
~~~~~^~~~~~~~~~~~~~~~
pokemonmaster.cpp:307:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &b[x]);
~~~~~^~~~~~~~~~~~~
pokemonmaster.cpp:314:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &ty);
~~~~~^~~~~~~~~~~
pokemonmaster.cpp:318:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &y, &x, &p);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
pokemonmaster.cpp:327:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &y, &x, &l);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
711 ms |
115796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
761 ms |
114800 KB |
Output is correct |
| 2 |
Correct |
973 ms |
114672 KB |
Output is correct |
| 3 |
Correct |
1321 ms |
110576 KB |
Output is correct |
| 4 |
Correct |
842 ms |
115696 KB |
Output is correct |
| 5 |
Correct |
1033 ms |
115952 KB |
Output is correct |
| 6 |
Incorrect |
1442 ms |
108272 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1286 ms |
132232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
711 ms |
115796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
711 ms |
115796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
