Submission #1189087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189087		tch1cherin	Sprinkler (JOI22_sprinkler)	C++20	41 / 100	4094 ms	126156 KiB

sprinkler

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")

template <typename T>
struct RMQ {
  vector<vector<T>> table;
  vector<int> logs;

  RMQ(vector<T> arr) {
    int size = int(arr.size());
    logs = vector<int>(size + 1);
    for (int i = 2; i <= size; i++) {
      logs[i] = logs[i / 2] + 1;
    }
    table = vector<vector<T>>(logs[size] + 1, vector<T>(size));
    table[0] = arr;
    for (int l = 0; l < logs[size]; l++) {
      for (int i = 0; i + (2 << l) <= size; i++) {
        table[l + 1][i] = min(table[l][i], table[l][i + (1 << l)]);
      }
    }
  }

  T query(int l, int r) {
    int t = logs[r - l];
    return min(table[t][l], table[t][r - (1 << t)]);
  }
};

struct segment_tree {
  int size, mod;
  vector<int> tag;

  segment_tree() = default;

  segment_tree(int N, int L) {
    size = N, mod = L;
    tag.assign(size * 2, 1);
  }

  void update(int l, int r, int value) {
    for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
      if (l & 1) {
        tag[l] = 1LL * tag[l] * value % mod;
        ++l;
      }
      if (r & 1) {
        --r;
        tag[r] = 1LL * tag[r] * value % mod;
      }
    }
  }

  int get(int pos) {
    int answer = 1;
    for (pos += size; pos > 0; pos >>= 1) {
      answer = 1LL * answer * tag[pos] % mod;
    }
    return answer;
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, L;
  cin >> N >> L;
  vector<vector<int>> graph(N);
  for (int i = 0; i < N - 1; i++) {
    int A, B;
    cin >> A >> B;
    --A, --B;
    graph[A].push_back(B);
    graph[B].push_back(A);
  }
  vector<int> H(N);
  for (int &x : H) {
    cin >> x;
  }
  vector<int> tin(N), tout(N), depth(N), pos(N), vtx_pos(N);
  vector<segment_tree> ds(N);
  vector<vector<int>> vtx(N);
  vector<pair<int, int>> tour;
  int cur = 0;
  auto DFS = [&](auto&& self, int u, int par) -> void {
    tin[u] = cur++;
    vtx_pos[u] = int(vtx[depth[u]].size());
    vtx[depth[u]].push_back(u);
    pos[u] = int(tour.size());
    tour.push_back({depth[u], u});
    for (int v : graph[u]) {
      if (v != par) {
        depth[v] = depth[u] + 1;
        self(self, v, u);
        tour.push_back({depth[u], u});
      }
    }
    tout[u] = cur;
  };
  DFS(DFS, 0, -1);
  for (int i = 0; i < N; i++) {
    ds[i] = segment_tree(int(vtx[i].size()), L);
  }
  RMQ rmq(tour);
  auto LCA = [&](int a, int b) -> int {
    if (pos[a] > pos[b]) {
      swap(a, b);
    }
    return rmq.query(pos[a], pos[b] + 1).second;
  };
  auto Dist = [&](int a, int b) -> int {
    return depth[a] + depth[b] - 2 * depth[LCA(a, b)];
  };
  int Q;
  cin >> Q;
  while (Q--) {
    int T;
    cin >> T;
    if (T == 1) {
      int X, D, W;
      cin >> X >> D >> W;
      --X;
      for (int d = max(0, depth[X] - D); d <= min(N - 1, depth[X] + D); d++) {
        int first, last;
        {
          int L = -1, R = int(vtx[d].size());
          while (R - L > 1) {
            int mid = (L + R) / 2;
            if (tin[vtx[d][mid]] < tin[X] && Dist(vtx[d][mid], X) > D) {
              L = mid;
            } else {
              R = mid;
            }
          }
          first = R;
        }
        {
          int L = first - 1, R = int(vtx[d].size());
          while (R - L > 1) {
            int mid = (L + R) / 2;
            if (tin[vtx[d][mid]] >= tin[X] && Dist(vtx[d][mid], X) > D) {
              R = mid;
            } else {
              L = mid;
            }
          }
          last = R;
        }
        ds[d].update(first, last, W);
      }      
    } else {
      int X;
      cin >> X;
      --X;
      cout << 1LL * H[X] * ds[depth[X]].get(vtx_pos[X]) % L << "\n";
    }
  }
}

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17