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 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;
}
};
int nz;
int ul[N * k * k * 3], ur[N * k * k * 3];
int ss[N * k * k * 3];
namespace nosr
{
void ubd(int tl, int tr, int x, int y, int pos)
{
ss[pos] += y;
if (tl == tr)
{
return;
}
int m = (tl + tr) / 2;
if (x <= m)
{
if (!ul[pos])
ul[pos] = ++nz;
ubd(tl, m, x, y, ul[pos]);
}
else
{
if (!ur[pos])
ur[pos] = ++nz;
ubd(m + 1, tr, x, y, ur[pos]);
}
}
int qry(int tl, int tr, int l, int r, int pos)
{
if (l > r)
return 0;
if (!ss[pos])
return 0;
if (tl == l && tr == r)
return ss[pos];
int m = (tl + tr) / 2;
return (qry(tl, m, l, min(m, r), ul[pos]) +
qry(m + 1, tr, max(m + 1, l), r, ur[pos]));
}
};
int t[N * 4];
void ubd(int tl, int tr, int x, int y, bool z, int pos)
{
if (!z)
{
if (!t[pos])
t[pos] = ++nz;
nosr::ubd(0, n * m, y, -1, t[pos]);
//treap::han(t[pos], y);
}
else
{
if (!t[pos])
t[pos] = ++nz;
nosr::ubd(0, n * m, y, 1, t[pos]);
//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 nosr::qry(0, n * m, 0, x, t[pos]);
//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;
ubd(1, n * m, x, hl, false, 1);
if (it != s[i].end())
{
ubd(1, n * m, *it, x, false, 1);
ubd(1, n * m, *it, hl, true, 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(0);
//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 (stderr)
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:305: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:315: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:360:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &b[x]);
~~~~~^~~~~~~~~~~~~
pokemonmaster.cpp:367:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &ty);
~~~~~^~~~~~~~~~~
pokemonmaster.cpp:371: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:380: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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |