Submission #243798

#TimeUsernameProblemLanguageResultExecution timeMemory
243798SamAndI want to be the very best too! (NOI17_pokemonmaster)C++17
100 / 100
3756 ms304068 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...