Submission #1067068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067068		juicy	Harvest (JOI20_harvest)	C++17	100 / 100	449 ms	73436 KiB

harvest

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;

using namespace __gnu_pbds;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long

template<class T>
using Tree = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5 + 5;

int n, m, l, c, q;
int a[N], b[N], tin[N], tout[N], root[N], pr[N];
bool in[N], spec[N];
int dep[N], res[N];
vector<int> g[N];
Tree<int> st;
vector<array<int, 2>> updates[N];
vector<array<int, 3>> queries[N];

void add(int x) {
  st.insert(x);
}

int qry(int i) {
  return st.order_of_key(i + 1);
}

int qry(int l, int r) {
  return qry(r) - qry(l - 1);
}

int add(int a, int b, int c) {
  a = (a + b) % c;
  if (a >= c) {
    a -= c;
  }
  if (a < 0) {
    a += c;
  }
  return a;
} 

int dis(int s, int t) {
  return c + add(a[t], -add(a[s], c, l), l);
}

int order;

void dfs(int u) {
  tin[u] = ++order;
  for (int v : g[u]) {
    if (!root[v]) {
      root[v] = root[u];
      dep[v] = dep[u] + dis(u, v);
      dfs(v);
    }
  }
  tout[u] = order;
}

void solve(vector<array<int, 3>> &que, vector<array<int, 2>> &ups, int len) {
  sort(que.begin(), que.end());
  sort(ups.begin(), ups.end());
  int j = 0;
  for (auto &[x, u, id] : que) {
    while (j < ups.size() && ups[j][0] <= x) {
      add(tin[ups[j][1]]);
      ++j;
    }
    res[id] = qry(tin[u], tout[u]);
    if (spec[id]) {
      x -= len;
    }
  }
  st.clear();
  sort(que.begin(), que.end());
  int k = 0;
  j = 0;
  for (auto [x, u, id] : que) {
    while (j < ups.size() && ups[j][0] <= x) {
      add(ups[j][0] % len);
      k += ups[j][0] / len;
      ++j;
    }
    if (spec[id]) {
      res[id] += (int) st.size() * (x / len) - k + qry(x % len);
    }
  }
  st.clear();
}

int32_t main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m >> l >> c;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }  
  for (int i = 1; i <= m; ++i) {
    cin >> b[i];
  }
  for (int i = 1; i <= n; ++i) {
    pr[i] = add(upper_bound(a + 1, a + n + 1, add(a[i], -c, l)) - a - 1, -1, n) + 1;
    g[pr[i]].push_back(i);
  }
  for (int i = 1; i <= n; ++i) {
    if (!root[i]) {
      int j = i;
      for (; !in[j]; j = pr[j]) {
        in[j] = 1;
      }
      root[j] = j;
      for (int k = i; k != j; k = pr[k]) {
        in[k] = 0;
      }
      dfs(j);
    }
  }
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    int r, x; cin >> r >> x;
    spec[i] = in[r];
    queries[root[r]].push_back({x + dep[r], r, i});
  }
  for (int i = 1; i <= m; ++i) {
    int p = add(upper_bound(a + 1, a + n + 1, b[i]) - a - 1, -1, n) + 1;
    updates[root[p]].push_back({dep[p] + add(b[i], -a[p], l), p});
  }
  for (int i = 1; i <= n; ++i) {
    if (root[i] == i) {
      int l = dep[pr[i]] + dis(pr[i], i);
      solve(queries[i], updates[i], l);
    }
  }
  for (int i = 1; i <= q; ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}

Compilation message (stderr)

harvest.cpp: In function 'void solve(std::vector<std::array<long long int, 3> >&, std::vector<std::array<long long int, 2> >&, long long int)':
harvest.cpp:78:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     while (j < ups.size() && ups[j][0] <= x) {
      |            ~~^~~~~~~~~~~~
harvest.cpp:92:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     while (j < ups.size() && ups[j][0] <= x) {
      |            ~~^~~~~~~~~~~~

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