#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> ppll;
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;
}
};
vector<ll> par, sz, root;
vector<ll> vals;
vector<ll> tin, tout, sons;
vector<vector<ll>> st, tree;
ll logn, t = -1;
ll getlog(ll n)
{
ll ans = 0;
while (n) ans++, n >>= 1;
return ans;
}
ll getpar(ll v)
{
if (par[v] == v)
return v;
return par[v] = getpar(par[v]);
}
void unit(ll v, ll u, ll r)
{
u = getpar(u);
if (v == u)
{
root[v] = r;
return;
}
if (sz[u] > sz[v]) swap(u, v);
par[u] = v;
sz[v] += sz[u];
root[v] = r;
}
void dfs(ll v)
{
tin[v] = ++t;
for (ll i = 0; i < tree[v].size(); i++)
{
ll u = tree[v][i];
dfs(u);
sons[v] += sons[u];
}
tout[v] = t;
}
ll getmaxl(ll ind, ll maxl)
{
for (ll i = logn - 1; i >= 0; i--)
if (vals[st[i][ind]] <= maxl)
ind = st[i][ind];
return ind;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll r, c, q;
cin >> r >> c >> q;
vector<vector<ll>> level(r, vector<ll>(c));
for (ll i = 0; i < r; i++)
for (ll j = 0; j < c; j++)
cin >> level[i][j];
vector<vector<ll>> pokemon(r, vector<ll>(c));
for (ll i = 0; i < r; i++)
for (ll j = 0; j < c; j++)
cin >> pokemon[i][j];
ll n = r * c;
vector<ppll> order(n);
for(ll i=0;i<r;i++)
for (ll j = 0; j < c; j++)
{
ll ind = i * c + j;
order[ind] = { level[i][j], {i, j} };
}
sort(order.begin(), order.end());
sz.resize(n, 1);
par.resize(n);
root.resize(n);
for (ll i = 0; i < n; i++)
par[i] = root[i] = i;
logn = getlog(n) + 1;
st.resize(logn, vector<ll>(n));
for (ll i = 0; i < n; i++)
st[0][i] = i;
for (ll i = 0; i < n; i++)
{
ll x = order[i].second.first, y = order[i].second.second, l = order[i].first, ind = x * c + y;
if (x && l > level[x - 1][y])
{
ll nei = (x - 1) * c + y;
nei = getpar(nei);
nei = root[nei];
st[0][nei] = ind;
unit(ind, nei, ind);
}
if (y && l > level[x][y - 1])
{
ll nei = x * c + y - 1;
nei = getpar(nei);
nei = root[nei];
st[0][nei] = ind;
unit(ind, nei, ind);
}
if (x < r - 1 && l > level[x + 1][y])
{
ll nei = (x + 1) * c + y;
nei = getpar(nei);
nei = root[nei];
st[0][nei] = ind;
unit(ind, nei, ind);
}
if (y<c - 1 && l > level[x][y + 1])
{
ll nei = x * c + y + 1;
nei = getpar(nei);
nei = root[nei];
st[0][nei] = ind;
unit(ind, nei, ind);
}
}
for (ll i = 1; i < logn; i++)
for (ll j = 0; j < n; j++)
st[i][j] = st[i - 1][st[i - 1][j]];
vals.resize(n);
for (ll i = 0; i < r; i++)
for (ll j = 0; j < c; j++)
vals[i * c + j] = level[i][j];
tree.resize(n);
for (ll i = 0; i < n; i++)
if (st[0][i] != i)
tree[st[0][i]].push_back(i);
ll bigroot = order.back().second.first * c + order.back().second.second;
tin.resize(n);
tout.resize(n);
sons.resize(n, 1);
dfs(bigroot);
seg s(n);
for(ll i=0;i<r;i++)
for (ll j = 0; j < c; j++)
s.update(tin[i * c + j], pokemon[i][j]);
while (q--)
{
ll type;
cin >> type;
if (type == 1)
{
ll x, y, p;
cin >> x >> y >> p;
x--, y--;
swap(x, y);
s.update(tin[x * c + y], p);
}
else
{
ll x, y, l;
cin >> x >> y >> l;
x--, y--;
swap(x, y);
if (level[x][y] > l)
{
cout << 0 << "\n";
continue;
}
ll ind = x * c + y;
ind = getmaxl(ind, l);
ll sum = s.q(tin[ind], tout[ind]);
if (sum == sons[ind] || sum == 0)
cout << 1 << "\n";
else
cout << 2 << "\n";
}
}
}
Compilation message
pokemonmaster.cpp: In function 'void dfs(ll)':
pokemonmaster.cpp:87: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]
87 | for (ll i = 0; i < tree[v].size(); i++)
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
18508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
17632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
17860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
18508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
18508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
