| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 960691 |
2024-04-10T23:31:43 Z |
Pring |
Harvest (JOI20_harvest) |
C++17 |
|
569 ms |
524288 KB |
#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];
ll lz[MXN];
__int128_t READ() {
long long x;
cin >> x;
return x;
}
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);
}
}
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();
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);
swap(tr[rt], tr[id]);
swap(lz[rt], lz[id]);
}
tr[id].clear();
}
void DFS(int id) {
vis[id] = true;
for (auto &[w, i] : edge[id]) {
if (vis[i]) continue;
DFS(i);
}
}
void GET_SR() {
FOR(i, 0, n) {
if (vis[i]) continue;
sr.insert(i);
DFS(i);
}
}
void CALC_MERGE(int id, bool f = true) {
vis[id] = false;
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];
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;
n = READ();
m = READ();
L = READ();
adf = READ();
FOR(i, 0, n) a[i] = READ();
FOR(i, 0, m) b[i] = READ();
// cin >> q;
q = READ();
FOR(i, 0, q) {
// cin >> qid[i] >> qt[i];
qid[i] = READ();
qt[i] = READ();
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;
}
Compilation message
harvest.cpp: In function 'void PUT_TREE()':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:86:9: note: in expansion of macro 'debug'
86 | debug(i, pp, x);
| ^~~~~
harvest.cpp: In function 'void GET_P()':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:99:9: note: in expansion of macro 'debug'
99 | debug(i, p[i], pt[i]);
| ^~~~~
harvest.cpp: In function 'void JELLY::CALC_MERGE(__int128, bool)':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:168:17: note: in expansion of macro 'debug'
168 | debug(i, x);
| ^~~~~
harvest.cpp: In function 'void JELLY::SOLVE(__int128)':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:174:9: note: in expansion of macro 'debug'
174 | debug(rt);
| ^~~~~
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:184:13: note: in expansion of macro 'debug'
184 | debug(cyc[i]);
| ^~~~~
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:186:17: note: in expansion of macro 'debug'
186 | debug(j);
| ^~~~~
harvest.cpp: In function 'void miku()':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:216:9: note: in expansion of macro 'debug'
216 | debug(i);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
49380 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
49624 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
77180 KB |
Output is correct |
| 2 |
Runtime error |
569 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
49380 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
49624 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
