| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 960570 |
2024-04-10T15:56:21 Z |
Pring |
Harvest (JOI20_harvest) |
C++17 |
|
95 ms |
55132 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 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;
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];
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;
ll val[MXN];
void init(int _n) {
n = _n;
fill(val, val + n, 0);
}
void modify(int id, ll v) {
for (id++; id <= n; id += (id & -id)) val[id] += v;
}
ll 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<ll> 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(C - (C - v[i]) % C - 1, 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;
ll 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;
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) cout << 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:76:3: note: in expansion of macro 'debug'
76 | 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:89:3: note: in expansion of macro 'debug'
89 | debug(i, p[i], pt[i]);
| ^~~~~
harvest.cpp: In function 'void CALC_CYC(std::vector<long long int>&, std::vector<std::pair<long long int, long long int> >&, ll)':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:113:4: note: in expansion of macro 'debug'
113 | debug(Q, s, aid, x / C);
| ^~~~~
harvest.cpp: In function 'void JELLY::CALC_MERGE(long long int, bool)':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:158:5: note: in expansion of macro 'debug'
158 | debug(i, x);
| ^~~~~
harvest.cpp: In function 'void JELLY::SOLVE(long long int)':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:164:3: note: in expansion of macro 'debug'
164 | debug(rt);
| ^~~~~
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:174:4: note: in expansion of macro 'debug'
174 | debug(cyc[i]);
| ^~~~~
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
harvest.cpp:176:5: note: in expansion of macro 'debug'
176 | 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:199:3: note: in expansion of macro 'debug'
199 | debug(i);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
41816 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
42076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
55132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
41816 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
42076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
