| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 960703 | Pring | Harvest (JOI20_harvest) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
// #define int long long
#define int __int128_t
#define ll __int128_t
#define lll __int128_t
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
// using ll = long long;
// using lll = __int128_t;
typedef pair<int, int> pii;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> PBDS_TREE;
const int MXN = 200005;
int n, m, L, adf, a[MXN], b[MXN], q, qid[MXN];
ll qt[MXN];
int p[MXN], pt[MXN];
ll ans[MXN];
vector<pii> edge[MXN];
vector<int> qry[MXN];
bitset<MXN> vis;
// PBDS_TREE tr[MXN];
vector<int> tr[MXN];
ll lz[MXN];
// __int128_t READ() {
// long long x;
// cin >> x;
// return x;
// }
istream &operator>>(istream &ss, __int128_t &x) {
long long y;
ss >> y;
x = y;
return ss;
}
ostream &operator<<(ostream &ss, __int128_t x) {
long long y = x;
ss << y;
return ss;
}
struct VSET {
bitset<MXN> b;
vector<int> v;
void init() {
b.reset();
v.clear();
}
void insert(int x) {
if (b[x]) return;
b[x] = true;
v.push_back(x);
}
void clear() {
for (auto &i : v) b[i] = false;
v.clear();
}
} sr;
struct BIT {
int n;
lll val[MXN];
void init(int _n) {
n = _n;
fill(val, val + n, 0);
}
void modify(int id, lll v) {
for (id++; id <= n; id += (id & -id)) val[id] += v;
}
lll query(int id) {
ll ans = 0;
for (; id > 0; id -= (id & -id)) ans += val[id];
return ans;
}
} B;
void PUT_TREE() {
FOR(i, 0, m) {
int pp = lower_bound(a, a + n, b[i]) - a - 1;
if (pp == -1) pp += n;
int x = (b[i] - a[pp] + L) % L;
debug(i, pp, x);
// tr[pp].insert(x);
tr[pp].push_back(x);
}
}
void GET_P() {
vector<pii> v;
FOR(i, 0, n) v.push_back(mp(a[i], i));
FOR(i, 0, n) v.push_back(mp(a[i] + L, i));
FOR(i, 0, n) {
auto pp = prev(lower_bound(v.begin(), v.end(), mp(a[i] + L - adf % L, MXN)));
p[i] = pp -> sc;
pt[i] = adf / L * L + (a[i] + L - pp -> fs);
debug(i, p[i], pt[i]);
edge[p[i]].push_back(mp(pt[i], i));
}
}
void CALC_CYC(vector<ll> &v, vector<pair<ll, int>> &vq, ll C) {
int n = v.size(), m = vq.size();
for (auto &[Q, aid] : vq) {
for (auto &i : v) {
if (Q - i < 0) continue;
ans[aid] += (Q - i) / C + 1;
}
}
// vector<lll> p(1, 0), pc(1, 0);
// for (auto &i : v) {
// p.push_back(p.back() + i);
// pc.push_back(pc.back() + (C - i) % C);
// }
// B.init(n);
// vector<pair<ll, int>> dist;
// FOR(i, 0, n) dist.push_back(mp((v[i] ? v[i] - 1 : LLONG_MAX), i));
// FOR(i, 0, m) dist.push_back(mp(vq[i].fs % C, -i - 1));
// sort(dist.begin(), dist.end());
// for (auto &[t, id] : dist) {
// if (id < 0) {
// id = -id - 1;
// auto [Q, aid] = vq[id];
// int s = lower_bound(v.begin(), v.end(), Q) - v.begin();
// if (s == 0) continue;
// lll x = Q * s - p[s] - (pc[s] + t * s + B.query(s));
// debug(Q, s, aid, x / C);
// ans[aid] += x / C + s;
// } else {
// B.modify(id, -C);
// }
// }
}
namespace JELLY {
void MERGE(int rt, int id, ll w) {
// if (tr[rt].size() >= tr[id].size()) {
// for (auto i : tr[id]) tr[rt].insert(i + lz[id] + w - lz[rt]);
// } else {
// lz[id] += w;
// for (auto i : tr[rt]) tr[id].insert(i + lz[rt] - w);
// tr[rt].swap(tr[id]);
// swap(lz[rt], lz[id]);
// }
// tr[id].clear();
for (auto &i : id) tr[rt].push_back(i + w);
}
void GET_SR() {
vector<int> ind(n), ban(n);
queue<int> q;
FOR(i, 0, n) ind[p[i]]++;
FOR(i, 0, n) if (ind[i] == 0) q.push(i);
while (q.size()) {
int id = q.front();
q.pop();
ban[id] = true;
if (--ind[p[id]] == 0) q.push(p[id]);
}
FOR(i, 0, n) {
if (ban[i]) continue;
sr.insert(i);
int now = i;
while (!ban[now]) {
ban[now] = true;
now = p[now];
}
}
}
void CALC_MERGE(int id, bool f = true) {
vis[id] = true;
for (auto &[w, i] : edge[id]) {
if (vis[i]) continue;
CALC_MERGE(i);
MERGE(id, i, w);
}
if (f) {
for (auto &i : qry[id]) {
// ll Q = qt[i] - lz[id];
ll Q = qt[i];
for (auto j : tr[id]) {
if (j <= Q) ans[i]++;
}
// int x = tr[id].order_of_key(Q + 1);
// debug(i, x);
// ans[i] += x;
}
}
}
void SOLVE(int rt) {
debug(rt);
CALC_MERGE(rt, false);
vector<ll> v;
for (auto i : tr[rt]) v.push_back(i + lz[rt]);
vector<pair<ll, int>> vq;
vector<int> cyc;
cyc.push_back(rt);
while (p[cyc.back()] != rt) cyc.push_back(p[cyc.back()]);
int acc = 0;
FOR(i, 0, cyc.size()) {
debug(cyc[i]);
for (auto &j : qry[cyc[i]]) {
debug(j);
vq.push_back(mp(qt[j] - acc, j));
}
acc += pt[cyc[i]];
}
CALC_CYC(v, vq, acc);
}
}
void miku() {
cin >> n >> m >> L >> adf;
FOR(i, 0, n) cin >> a[i];
FOR(i, 0, m) cin >> b[i];
cin >> q;
FOR(i, 0, q) {
cin >> qid[i] >> qt[i];
qid[i]--;
qry[qid[i]].push_back(i);
}
PUT_TREE();
GET_P();
JELLY::GET_SR();
for (auto &i : sr.v) {
debug(i);
JELLY::SOLVE(i);
}
FOR(i, 0, q) {
assert(ans[i] <= LLONG_MAX);
cout << (long long) ans[i] << '\n';
}
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
miku();
return 0;
}