Submission #294511

#	Time	Username	Problem	Language	Result	Execution time	Memory
294511		rama_pang	I want to be the very best too! (NOI17_pokemonmaster)	C++14	100 / 100	4674 ms	138640 KiB

pokemonmaster

#include <bits/stdc++.h>
using namespace std;

class Fenwick {
 public:
  int sz;
  vector<int> tree;
  vector<pair<int, int>> coords;

  Fenwick() {}
  void AddCoordinate(pair<int, int> x) {
    coords.emplace_back(x);
  }
  void Build() {
    sort(begin(coords), end(coords));
    coords.resize(unique(begin(coords), end(coords)) - begin(coords));
    sz = coords.size();
    tree.assign(sz, 0);
  }
  void Modify(pair<int, int> pi, int x) {
    int p = lower_bound(begin(coords), end(coords), pi) - begin(coords);
    assert(p != (int) coords.size() && coords[p] == pi);
    for (int i = p; i < sz; i |= i + 1) {
      tree[i] += x;
    }
  }
  int Query(pair<int, int> pi) {
    int p = upper_bound(begin(coords), end(coords), pi) - begin(coords);
    int res = 0;
    for (int i = p; i > 0; i &= i - 1) {
      res += tree[i - 1];
    }
    return res;
  }
};

class RangeTree {
 public:
  int sz;
  vector<Fenwick> tree;

  RangeTree() {}
  RangeTree(int sz) : sz(sz), tree(2 * sz) {}

  void AddCoordinate(int i, int x) {
    for (int p = i + sz; p > 0; p /= 2) {
      tree[p].AddCoordinate({x, i});
    }
  }
  void Build() {
    for (int i = 0; i < 2 * sz; i++) {
      tree[i].Build();
    }
  }
  void Modify(int i, int x, int t) {
    for (int p = i + sz; p > 0; p /= 2) {
      tree[p].Modify({x, i}, t);
    }
  }
  int Query(int ql, int qr) {
    int res = (qr - ql);
    for (int l = ql + sz, r = qr + sz; l < r; l /= 2, r /= 2) {
      if (l & 1) res -= tree[l++].Query({qr, -1});
      if (r & 1) res -= tree[--r].Query({qr, -1});
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int R, C, Q;
  cin >> R >> C >> Q;

  vector<array<int, 3>> levels;
  vector<vector<int>> L(R, vector<int>(C));
  vector<vector<int>> P(R, vector<int>(C));

  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      cin >> L[i][j];
      levels.push_back({L[i][j], i, j});
    }
  }
  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      cin >> P[i][j];
    }
  }

  const int BITS = 16;
  vector<vector<int>> adj(R * C);
  vector<vector<int>> parent(R * C, vector<int>(BITS, -1));

  vector<int> comp(R * C);
  iota(begin(comp), end(comp), 0);
  function<int(int)> FindComp = [&](int x) {
    return comp[x] == x ? x : comp[x] = FindComp(comp[x]);
  };

  const vector<int> dx = {0, 1, 0, -1};
  const vector<int> dy = {1, 0, -1, 0};
  const auto Inside = [&](int x, int y) {
    return 0 <= x && x < R && 0 <= y && y < C;
  };

  sort(begin(levels), end(levels));
  for (const auto &lv : levels) {
    int x = lv[1], y = lv[2];
    for (int d = 0; d < 4; d++) {
      int nx = x + dx[d];
      int ny = y + dy[d];
      if (Inside(nx, ny) && L[nx][ny] < L[x][y]) {
        int u = FindComp(nx * C + ny);
        if (u != x * C + y) {
          comp[u] = x * C + y;
          parent[u][0] = x * C + y;
          adj[x * C + y].emplace_back(u);
        }
      }
    }
  }

  vector<int> st(R * C), et(R * C);
  int timer = 0;
  function<void(int)> Dfs = [&](int u) {
    st[u] = timer++;
    for (auto v : adj[u]) {
      Dfs(v);
    }
    et[u] = timer;
  };
  Dfs(FindComp(0));
  for (int j = 1; j < BITS; j++) {
    for (int i = 0; i < R * C; i++) {
      if (parent[i][j - 1] != -1) {
        parent[i][j] = parent[parent[i][j - 1]][j - 1];
      } else {
        parent[i][j] = parent[i][j - 1];
      }
    }
  } 

  RangeTree rtree(R * C);
  const int M = 50005;
  vector<int> A(R * C);
  vector<set<int>> occ(M);
  for (int i = 0; i < M; i++) {
    occ[i].emplace(R * C);
  }
  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      A[st[i * C + j]] = P[i][j];
      occ[P[i][j]].emplace(st[i * C + j]);
    }
  }
  for (int i = 0; i < M; i++) {
    for (auto j : occ[i]) if (j < R * C) {
      rtree.AddCoordinate(j, *occ[i].upper_bound(j));
    }
  }

  auto AddCoordinate = [&](int i, int x) {
    auto it = occ[A[i]].find(i);
    if (it != begin(occ[A[i]])) {
      rtree.AddCoordinate(*prev(it), *it);
      rtree.AddCoordinate(*prev(it), *next(it));
    }
    rtree.AddCoordinate(*it, *next(it));
    occ[A[i]].erase(it);
    A[i] = x;
    occ[A[i]].insert(i);
    it = occ[A[i]].find(i);
    rtree.AddCoordinate(*it, *next(it));
    if (it != begin(occ[A[i]])) {
      rtree.AddCoordinate(*prev(it), *next(it));
      rtree.AddCoordinate(*prev(it), *it);
    }    
  };

  vector<tuple<int, int, int, int>> queries;
  for (int i = 0; i < Q; i++) {
    int T, X, Y, Z;
    cin >> T >> X >> Y >> Z;
    queries.push_back(make_tuple(T, X, Y, Z));
    X--, Y--;
    swap(X, Y);
    int P = X * C + Y;
    if (T == 1) {
      AddCoordinate(st[P], Z);
    }
  }

  rtree.Build();
  A.assign(R * C, 0);
  occ.assign(M, set<int>());
  for (int i = 0; i < M; i++) {
    occ[i].emplace(R * C);
  }
  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      A[st[i * C + j]] = P[i][j];
      occ[P[i][j]].emplace(st[i * C + j]);
    }
  }
  for (int i = 0; i < M; i++) {
    for (auto j : occ[i]) if (j < R * C) {
      rtree.Modify(j, *occ[i].upper_bound(j), +1);
    }
  }

  auto Update = [&](int i, int x) {
    auto it = occ[A[i]].find(i);
    if (it != begin(occ[A[i]])) {
      rtree.Modify(*prev(it), *it, -1);
      rtree.Modify(*prev(it), *next(it), +1);
    }
    rtree.Modify(*it, *next(it), -1);
    occ[A[i]].erase(it);
    A[i] = x;
    occ[A[i]].insert(i);
    it = occ[A[i]].find(i);
    rtree.Modify(*it, *next(it), +1);
    if (it != begin(occ[A[i]])) {
      rtree.Modify(*prev(it), *next(it), -1);
      rtree.Modify(*prev(it), *it, +1);
    }
  };

  auto Query = [&](int l, int r) {
    return rtree.Query(l, r);
  };

  for (int i = 0; i < Q; i++) {
    int T, X, Y, Z;
    tie(T, X, Y, Z) = queries[i];
    X--, Y--;
    swap(X, Y);
    int P = X * C + Y;
    if (T == 1) {
      Update(st[P], Z);
    } else if (T == 2) {
      for (int j = BITS - 1; j >= 0; j--) {
        int par = parent[P][j];
        if (par != -1 && L[par / C][par % C] <= Z) {
          P = par;
        }
      }
      cout << (L[P / C][P % C] <= Z ? Query(st[P], et[P]) : 0) << "\n";
    }
  }
  return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 29 / 29