Submission #1214430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214430		abczz	Harvest (JOI20_harvest)	C++20	25 / 100	418 ms	243468 KiB

harvest

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <array>
#include <map>
#include <queue>
#define ll long long

using namespace std;

random_device rd;
mt19937 mt(rd());
queue <ll> Q;
ll rnd() {return mt() % (ll)1e9; }

array<ll, 3> operator+(array<ll, 3> a, array<ll, 3> b) {
  return {a[0]+b[0], a[1]+b[1], a[2]+b[2]};
};
struct Treap{
  ll root;
  struct Node { ll v = -1, p = -1, sz = 1, l = 0, r = 0; };
  vector <Node> node = {{-1, -1, 0, 0, 0}};
  void split_lb(ll treap, ll &l, ll &r, ll x) {
    if (!treap) {
      l = r = 0;
      return;
    }
    auto &N = node[treap];
    if (N.v < x) {
      split_lb(N.r, N.r, r, x);
      l = treap;
    }
    else {
      split_lb(N.l, l, N.l, x);
      r = treap;
    }
    N.sz = node[N.l].sz + node[N.r].sz + 1;
  }
  void split_sz(ll treap, ll &l, ll &r, ll x) {
    if (!treap) {
      l = r = 0;
      return;
    }
    auto &N = node[treap];
    if (x <= node[N.l].sz) {
      split_sz(N.l, l, N.l, x);
      r = treap;
    }
    else {
      split_sz(N.r, N.r, r, x-node[N.l].sz-1);
      l = treap;
    }
    N.sz = node[N.l].sz + node[N.r].sz + 1;
  }
  void merge(ll &treap, ll l, ll r) {
    if (!l) {
      treap = r;
      return;
    }
    if (!r) {
      treap = l;
      return;
    }
    if (node[l].p < node[r].p) {
      merge(node[l].r, node[l].r, r);
      treap = l;
    }
    else {
      merge(node[r].l, l, node[r].l);
      treap = r;
    }
    auto &N = node[treap];
    N.sz = node[N.l].sz + node[N.r].sz + 1;
  }
  void insert(ll &treap, ll t) {
    if (!treap) {
      treap = t;
      return;
    }
    auto &N = node[treap];
    if (N.p < node[t].p) {
      if (N.v < node[t].v) insert(N.r, t);
      else insert(N.l, t);
      N.sz = node[N.l].sz + node[N.r].sz + 1;
    }
    else {
      split_lb(treap, node[t].l, node[t].r, node[t].v);
      treap = t;
      node[t].sz = node[node[t].l].sz + node[node[t].r].sz + 1;
    }
  }
  ll query(ll treap, ll x) {
    if (!treap) return 0;
    auto N = node[treap];
    if (N.v < x) return node[N.l].sz + 1 + query(N.r, x);
    else return query(N.l, x);
  }
  void addNode(ll w) {
    node.push_back({w, rnd(), 1, 0, 0});
    if (node.size() == 2) root = 1;
    else insert(root, node.size()-1);
  }
  void delNode(ll w) {
    ll t1, t2, t3;
    split_lb(root, t1, t2, w);
    split_sz(t2, t2, t3, 1);
    merge(root, t1, t3);
  }
  void clear() {
    node = {{-1, -1, 0, 0, 0}};
    root = 0;
  }
}T[400000];
ll cyc_len, s;
struct SegTree{
  Treap st[800000];
  ll sum[800000], cnt[800000];
  vector <ll> X;
  void init(ll sz) {
    for (int i=0; i<4*sz; ++i) {
      sum[i] = cnt[i] = 0;
      st[i].clear();
    }
  }
  void insert(ll id, ll l, ll r, ll q, ll w) {
    st[id].addNode(w);
    if (l == r) {
      sum[id] += (X[l] >= 0 ? X[l] / cyc_len : (X[l]-cyc_len+1)/cyc_len), ++cnt[id];
      return;
    }
    ll mid = (l+r)/2;
    if (q <= X[mid]) insert(id*2, l, mid, q, w);
    else insert(id*2+1, mid+1, r, q, w);
    sum[id] = sum[id*2] + sum[id*2+1];
    cnt[id] = cnt[id*2] + cnt[id*2+1];
  }
  void del(ll id, ll l, ll r, ll q, ll w) {
    st[id].delNode(w);
    if (l == r) {
      sum[id] -= (X[l] >= 0 ? X[l] / cyc_len : (X[l]-cyc_len+1)/cyc_len), --cnt[id];
      return;
    }
    ll mid = (l+r)/2;
    if (q <= X[mid]) del(id*2, l, mid, q, w);
    else del(id*2+1, mid+1, r, q, w);
    sum[id] = sum[id*2] + sum[id*2+1];
    cnt[id] = cnt[id*2] + cnt[id*2+1];
  }
  array<ll, 3> query(ll id, ll l, ll r, ll q, ll w) {
    if (q < X[l]) return {0, 0, 0};
    if (q >= X[r]) return {st[id].query(st[id].root, w), sum[id], cnt[id]};
    ll mid = (l+r)/2;
    return query(id*2, l, mid, q, w) + query(id*2+1, mid+1, r, q, w);
  }
  void clear() {
    X.clear();
  }
}ST;
ll n, m, l, c, q;
map <ll, ll> mp;
vector <array<ll, 2>> query[400000];
vector <ll> adj[400000];
ll A[200000], B[200000], P[400000], W[400000], in[400000], sz[400000], delta[400000];
ll a, b, F[200000];

void bfs(ll u) {
  ll mx = -1, id = -1;
  for (auto v : adj[u]) {
    if (sz[v] > mx) mx = sz[v], id = v;
  }
  if (id != -1) {
    delta[u] = delta[id] + W[id];
    swap(T[u], T[id]);
  }
  for (auto v : adj[u]) {
    if (v == id) continue;
    for (int j=1; j<T[v].node.size(); ++j) {
      T[u].addNode(T[v].node[j].v+delta[v]+W[v]-delta[u]);
    }
  }
  if (u >= n) T[u].addNode(0);
}

ll prev(ll u) {
  u %= l;
  if (u < 0) u += l;
  if (u < A[0]) u += (ll)((A[0]-u+l-1)/l) * l;
  return lower_bound(A, A+n, u+1)-A-1;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> m >> l >> c;
  for (int i=0; i<n; ++i) cin >> A[i];
  for (int i=0; i<m; ++i) cin >> B[i];
  cin >> q;
  for (int i=0; i<q; ++i) {
    cin >> a >> b;
    --a;
    query[a].push_back({b, i});
  }
  for (int i=0; i<m; ++i) P[n+i] = prev(B[i]), W[n+i] = (B[i]-A[P[n+i]]+l) % l, ++in[P[n+i]];
  for (int i=0; i<n; ++i) {
    P[i] = prev(A[i]-c), ++in[P[i]];
    ll k = ((A[i]-A[P[i]]+l)%l);
    if (k < c) k += (ll)((c-k+l-1)/l) * l;
    W[i] = k;
  }
  for (int i=0; i<n+m; ++i) {
    sz[i] = 1;
    if (!in[i]) Q.push(i);
  }
  while (!Q.empty()) {
    auto u = Q.front();
    Q.pop();
    bfs(u);
    for (auto [x, id] : query[u]) {
      F[id] = T[u].query(T[u].root, x-delta[u]+1);
    }
    --in[P[u]];
    adj[P[u]].push_back(u);
    sz[P[u]] += sz[u];
    if (!in[P[u]]) Q.push(P[u]);
  }
  for (int i=0; i<n; ++i) {
    if (!in[i]) continue;
    ST.clear();
    mp.clear();
    ll u = i;
    cyc_len = 0, s = 0;
    while (true) {
      cyc_len += W[u];
      in[u] = 0;
      bfs(u);
      u = P[u];
      if (u == i) break;
    }
    while (true) {
      for (int j=1; j<T[u].node.size(); ++j) {
        ++mp[T[u].node[j].v+s+delta[u]];
        ++mp[T[u].node[j].v-cyc_len+s+delta[u]];
      }
      (s += (cyc_len-W[u])) %= cyc_len;
      u = P[u];
      if (u == i) break;
    }
    for (auto [x, y] : mp) ST.X.push_back(x);
    if (ST.X.empty()) continue;
    ST.init(ST.X.size());
    s = 0;
    while (true) {
      for (int j=1; j<T[u].node.size(); ++j) {
        ST.insert(1, 0, ST.X.size()-1, T[u].node[j].v+s+delta[u], (T[u].node[j].v+s+delta[u]) % cyc_len);
      }
      (s += (cyc_len-W[u])) %= cyc_len;
      u = P[u];
      if (u == i) break;
    }
    s = 0;
    while (true) {
      ll dist = (cyc_len-s) % cyc_len;
      for (auto [x, id] : query[u]) {
        auto res1 = ST.query(1, 0, ST.X.size()-1, x-dist, (x % cyc_len)-dist+1);
        auto res2 = ST.query(1, 0, ST.X.size()-1, x-dist, ((x-dist+cyc_len) % cyc_len)+1);
        F[id] = res1[2] + res1[2] * (ll)(x-dist >= 0 ? ((x-dist)/cyc_len) : (x-dist-cyc_len+1)/cyc_len) - res1[1] - (res1[2] - res2[0]);
      }
      (s += (cyc_len-W[u])) %= cyc_len;
      u = P[u];
      if (u == i) break;
      for (int j=1; j<T[u].node.size(); ++j) {
        ST.del(1, 0, ST.X.size()-1, T[u].node[j].v+s+delta[u], (T[u].node[j].v+s+delta[u]) % cyc_len);
        ST.insert(1, 0, ST.X.size()-1, T[u].node[j].v-cyc_len+s+delta[u], (T[u].node[j].v+s+delta[u]) % cyc_len);
      }
    }
  }
  for (int i=0; i<q; ++i) cout << F[i] << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 0 / 75