oj.uz

Submission #294511

# Submission time Handle Problem Language Result Execution time Memory
294511 2020-09-09T03:17:13 Z rama_pang I want to be the very best too! (NOI17_pokemonmaster) C++14
100 / 100
 4674 ms 138640 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 41904 KB Output is correct
2 Correct 381 ms 43440 KB Output is correct
3 Correct 425 ms 43948 KB Output is correct
4 Correct 266 ms 43668 KB Output is correct
5 Correct 372 ms 43312 KB Output is correct
6 Correct 396 ms 42288 KB Output is correct
7 Correct 220 ms 42928 KB Output is correct
8 Correct 338 ms 43312 KB Output is correct
9 Correct 231 ms 42928 KB Output is correct
10 Correct 407 ms 43312 KB Output is correct
11 Correct 388 ms 43440 KB Output is correct
12 Correct 411 ms 43272 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 39728 KB Output is correct
2 Correct 344 ms 40112 KB Output is correct
3 Correct 385 ms 40396 KB Output is correct
4 Correct 239 ms 42608 KB Output is correct
5 Correct 346 ms 42736 KB Output is correct
6 Correct 373 ms 41544 KB Output is correct
7 Correct 237 ms 38812 KB Output is correct
8 Correct 352 ms 39024 KB Output is correct
9 Correct 266 ms 38548 KB Output is correct
10 Correct 420 ms 39148 KB Output is correct
11 Correct 390 ms 38512 KB Output is correct
12 Correct 420 ms 39152 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 708 ms 51236 KB Output is correct
2 Correct 2127 ms 95020 KB Output is correct
3 Correct 3222 ms 133212 KB Output is correct
4 Correct 3282 ms 135888 KB Output is correct
5 Correct 2292 ms 97884 KB Output is correct
6 Correct 869 ms 52832 KB Output is correct
7 Correct 2297 ms 93832 KB Output is correct
8 Correct 2278 ms 93604 KB Output is correct
9 Correct 2299 ms 93804 KB Output is correct
10 Correct 2318 ms 94088 KB Output is correct
11 Correct 2248 ms 93532 KB Output is correct
12 Correct 2262 ms 93908 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 41904 KB Output is correct
2 Correct 381 ms 43440 KB Output is correct
3 Correct 425 ms 43948 KB Output is correct
4 Correct 266 ms 43668 KB Output is correct
5 Correct 372 ms 43312 KB Output is correct
6 Correct 396 ms 42288 KB Output is correct
7 Correct 220 ms 42928 KB Output is correct
8 Correct 338 ms 43312 KB Output is correct
9 Correct 231 ms 42928 KB Output is correct
10 Correct 407 ms 43312 KB Output is correct
11 Correct 388 ms 43440 KB Output is correct
12 Correct 411 ms 43272 KB Output is correct
13 Correct 761 ms 52004 KB Output is correct
14 Correct 2900 ms 98864 KB Output is correct
15 Correct 4646 ms 136264 KB Output is correct
16 Correct 3512 ms 137228 KB Output is correct
17 Correct 2860 ms 98844 KB Output is correct
18 Correct 953 ms 51672 KB Output is correct
19 Correct 1865 ms 93484 KB Output is correct
20 Correct 2723 ms 98876 KB Output is correct
21 Correct 2131 ms 95440 KB Output is correct
22 Correct 3000 ms 95644 KB Output is correct
23 Correct 2971 ms 98948 KB Output is correct
24 Correct 2525 ms 87396 KB Output is correct

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 41904 KB Output is correct
2 Correct 381 ms 43440 KB Output is correct
3 Correct 425 ms 43948 KB Output is correct
4 Correct 266 ms 43668 KB Output is correct
5 Correct 372 ms 43312 KB Output is correct
6 Correct 396 ms 42288 KB Output is correct
7 Correct 220 ms 42928 KB Output is correct
8 Correct 338 ms 43312 KB Output is correct
9 Correct 231 ms 42928 KB Output is correct
10 Correct 407 ms 43312 KB Output is correct
11 Correct 388 ms 43440 KB Output is correct
12 Correct 411 ms 43272 KB Output is correct
13 Correct 229 ms 39728 KB Output is correct
14 Correct 344 ms 40112 KB Output is correct
15 Correct 385 ms 40396 KB Output is correct
16 Correct 239 ms 42608 KB Output is correct
17 Correct 346 ms 42736 KB Output is correct
18 Correct 373 ms 41544 KB Output is correct
19 Correct 237 ms 38812 KB Output is correct
20 Correct 352 ms 39024 KB Output is correct
21 Correct 266 ms 38548 KB Output is correct
22 Correct 420 ms 39148 KB Output is correct
23 Correct 390 ms 38512 KB Output is correct
24 Correct 420 ms 39152 KB Output is correct
25 Correct 708 ms 51236 KB Output is correct
26 Correct 2127 ms 95020 KB Output is correct
27 Correct 3222 ms 133212 KB Output is correct
28 Correct 3282 ms 135888 KB Output is correct
29 Correct 2292 ms 97884 KB Output is correct
30 Correct 869 ms 52832 KB Output is correct
31 Correct 2297 ms 93832 KB Output is correct
32 Correct 2278 ms 93604 KB Output is correct
33 Correct 2299 ms 93804 KB Output is correct
34 Correct 2318 ms 94088 KB Output is correct
35 Correct 2248 ms 93532 KB Output is correct
36 Correct 2262 ms 93908 KB Output is correct
37 Correct 761 ms 52004 KB Output is correct
38 Correct 2900 ms 98864 KB Output is correct
39 Correct 4646 ms 136264 KB Output is correct
40 Correct 3512 ms 137228 KB Output is correct
41 Correct 2860 ms 98844 KB Output is correct
42 Correct 953 ms 51672 KB Output is correct
43 Correct 1865 ms 93484 KB Output is correct
44 Correct 2723 ms 98876 KB Output is correct
45 Correct 2131 ms 95440 KB Output is correct
46 Correct 3000 ms 95644 KB Output is correct
47 Correct 2971 ms 98948 KB Output is correct
48 Correct 2525 ms 87396 KB Output is correct
49 Correct 756 ms 51640 KB Output is correct
50 Correct 2884 ms 98348 KB Output is correct
51 Correct 4674 ms 135940 KB Output is correct
52 Correct 3594 ms 138640 KB Output is correct
53 Correct 3003 ms 101304 KB Output is correct
54 Correct 1147 ms 52832 KB Output is correct
55 Correct 1976 ms 91352 KB Output is correct
56 Correct 2862 ms 97628 KB Output is correct
57 Correct 2255 ms 93624 KB Output is correct
58 Correct 3093 ms 93532 KB Output is correct
59 Correct 3058 ms 96996 KB Output is correct
60 Correct 2601 ms 85456 KB Output is correct