#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> ppll;
vector<ll> head, group, vals, tin, tout;
vector<vector<ll>> tree, st;
ll t = -1, logsz;
struct seg
{
vector<ll> a;
ll sz;
seg(ll n)
{
for (sz = 1; sz < n; sz <<= 1);
a.resize(sz * 2, 0);
}
void update(ll ind, ll x)
{
ind += sz;
a[ind] = x;
for (ind >>= 1; ind; ind >>= 1)
a[ind] = a[ind * 2] + a[ind * 2 + 1];
}
ll q(ll l, ll r)
{
l += sz, r += sz;
ll ans = 0;
while (l<=r)
{
if (l % 2 == 1) ans += a[l++];
if (r % 2 == 0) ans += a[r--];
l >>= 1;
r >>= 1;
}
return ans;
}
};
ll gethead(ll v)
{
if (head[v] == v)
return v;
return gethead(head[v]);
}
void unit(ll v, ll u)
{
u = gethead(u);
if (head[u] != v)
head[u] = v, group[v] += group[u], st[0][u] = v;
}
ll getlog(ll n)
{
ll ans = 0;
while (n)
{
n >>= 1;
ans++;
}
return ans;
}
ll getpar(ll ind, ll maxl)
{
for (ll i = logsz - 1; i >= 0; i--)
if (vals[st[i][ind]] <= maxl)
ind = st[i][ind];
if (vals[st[0][ind]] <= maxl)
ind = st[0][ind];
return ind;
}
void dfs(ll v, ll p)
{
tin[v] = ++t;
for (ll i = 0; i < tree[v].size(); i++)
{
ll u = tree[v][i];
if (u == p) continue;
dfs(u, v);
}
tout[v] = t;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll r, c, q;
cin >> r >> c >> q;
vector<vector<ll>> l(r, vector<ll>(c)), p(r, vector<ll>(c));
for (ll i = 0; i < r; i++)
for (ll j = 0; j < c; j++)
cin >> l[i][j];
for (ll i = 0; i < r; i++)
for (ll j = 0; j < c; j++)
cin >> p[i][j];
vector<ppll> order;
for (ll i = 0; i < r; i++)
for (ll j = 0; j < c; j++)
order.push_back({ l[i][j], {i, j} });
sort(order.begin(), order.end());
ll sz = r * c;
group.resize(sz, 1);
head.resize(sz);
for (ll i = 0; i < sz; i++)
head[i] = i;
logsz = getlog(sz) + 1;
st.resize(logsz, vector<ll>(sz));
for (ll i = 0; i < sz; i++)
st[0][i] = i;
for (ll i = 0; i < sz; i++)
{
ll x = order[i].second.first, y = order[i].second.second;
ll ind = x * c + y;
if (x && l[x][y] > l[x - 1][y])
unit(ind, ind - c);
if (y && l[x][y] > l[x][y - 1])
unit(ind, ind - 1);
if (x<r - 1 && l[x][y] > l[x + 1][y])
unit(ind, ind + c);
if (y<c - 1 && l[x][y] > l[x][y + 1])
unit(ind, ind + 1);
}
for (ll i = 1; i < logsz; i++)
for (ll j = 0; j < sz; j++)
st[i][j] = st[i - 1][st[i - 1][j]];
vals.resize(r * c);
for (ll i = 0; i < r; i++)
for (ll j = 0; j < c; j++)
vals[i * c + j] = l[i][j];
ll root = order.back().second.first * c + order.back().second.second;
tree.resize(r * c);
for (ll i = 0; i < r * c; i++)
{
tree[i].push_back(st[0][i]);
tree[st[0][i]].push_back(i);
}
tin.resize(sz);
tout.resize(sz);
dfs(root, root);
seg s(sz);
for (ll i = 0; i < r; i++)
for (ll j = 0; j < c; j++)
s.update(tin[i * c + j], p[i][j]);
while (q--)
{
ll type;
cin >> type;
if (type == 1)
{
ll x, y, newp;
cin >> x >> y >> newp;
x--, y--;
swap(x, y);
ll ind = x * c + y;
s.update(tin[ind], newp);
}
else
{
ll x, y, newl;
cin >> x >> y >> newl;
x--, y--;
swap(x, y);
if (l[x][y] > newl)
{
cout << 0 << "\n";
continue;
}
ll ind = x * c + y;
ind = getpar(ind, newl);
ll ans = s.q(tin[ind], tout[ind]);
if (ans != group[ind] && ans!=0)
cout << 2 << "\n";
else
cout << 1 << "\n";
}
}
}
Compilation message
pokemonmaster.cpp: In function 'void dfs(ll, ll)':
pokemonmaster.cpp:93:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (ll i = 0; i < tree[v].size(); i++)
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
17552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
17396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
185 ms |
19280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
17552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
17552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
