| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1089735 |
2024-09-17T04:57:46 Z |
phong |
Harvest (JOI20_harvest) |
C++17 |
|
2035 ms |
524288 KB |
#include<bits/stdc++.h>
#define ll long long
//#define int long long
const int nmax = 4e5 + 5, M = 3e6 + 5;
const ll oo = 1e9 + 5, base = 311;
const int lg = 62, tx = 26;
const ll mod = 1e9 + 7, mod2 = 1e9+3;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
#define NAME code
using namespace std;
ll n, m, L, C;
pii a[nmax], b[nmax];
pii c[nmax];
vector<pii> inp[nmax], out[nmax], adj[nmax];
map<int, ll>mp[nmax];
bool vis[nmax];
vector<int> tmp;
int root;
void dfs(int u, int p){
vis[u] = 1;
tmp.push_back(u);
for(auto [w, v] : adj[u]){
if(v == p) continue;
if(vis[v]) root = v;
else{
vis[v] = 1;
dfs(v, u);
}
}
}
/*
3 2 7 3
1 4 6
0 5
3
1 7
2 3
3 8
*/
int root_2, par[nmax];
ll dis[nmax];
ll len = 0;
void dfs_2(int u){
vis[u] = 1;
for(auto [w, v] : out[u]){
// cout << u << ' ' << v << ' ' << mp[v][u] << endl;
if(vis[v]){
root_2 = u;
continue;
}
dis[v] = dis[u] + mp[v][u];
par[v] = u;
dfs_2(v);
}
}
int tour[nmax], st[nmax], en[nmax], Time = 0;
void dfs_3(int u, int p){
tour[++Time] = u;
st[u] = Time;
vis[u] = 1;
for(auto [w, v]: out[u]){
if(v == p || vis[v]) continue;
// cerr<< u << ' ' << v << endl;
dfs_3(v, u);
}
en[u] = Time;
}
ll ans[nmax];
vector<ll> tree[1 << 20];
void build(int id, int l, int r){
tree[id].clear();
if(l == r){
int x = tour[l];
if(x > n) tree[id].push_back(dis[x]);
return;
}
int mid = r + l >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
tree[id].resize(tree[id << 1].size() + tree[id << 1 | 1].size());
merge(tree[id << 1].begin(), tree[id << 1].end(), tree[id << 1 | 1].begin(), tree[id << 1 | 1].end(), tree[id].begin());
}
int get(int id, int l, int r, int u, int v, ll k){
if(tree[id].empty()) return 0;
if(l >= u && r <= v){
return upper_bound(tree[id].begin(), tree[id].end(), k) - tree[id].begin();
}
int mid = r + l >> 1;
if(mid < u) return get(id << 1 | 1, mid + 1, r, u, v, k);
if(mid + 1 > v) return get(id << 1, l, mid, u, v, k);
return get(id << 1, l, mid, u, v, k) +get(id << 1 | 1, mid + 1, r, u, v, k);
}
vector<pii> Q[nmax];
ll dos[nmax];
void dfs_4(int u){
vis[u] = 1;
for(auto [w,v] : inp[u]){
len += w;
if(vis[v]) continue;
dos[v] = dos[u] + w;
dfs_4(v);
}
}
vector<int> hos[nmax];
void dfs_5(int u, int p){
if(u > n) hos[p].push_back(u);
for(auto [w, v] : out[u]){
if(vis[v]) continue;
dfs_5(v,p);
}
}
struct cay2{
ll f[M + 5];
vector<int> tmp;
void clear(){
for(auto p : tmp) f[p] = 0;
tmp.clear();
}
void update(int u, ll val){
for(; u <= M; u += u &-u) f[u] += val, tmp.push_back(u);
}
ll get(int u){
ll res = 0;
for(; u; u -= u&-u) res += f[u];
return res;
}
}str[2];
struct cay3{
vector<int> tmp;
vector<int> f[M + 5], note[M +5];
void Fake_update(int x, int y){
for(; x <= M; x += x&-x) note[x].push_back(y), tmp.push_back(x);
}
void Fake_get(int x, int y){
for(; x; x -= x&-x) note[x].push_back(y), tmp.push_back(x);
}
void update(int x, int y, int val){
for(; x <= M; x += x &-x){
if(f[x].empty()){
sort(note[x].begin(), note[x].end());
note[x].erase(unique(note[x].begin(), note[x].end()), note[x].end());
f[x].resize(note[x].size() + 2);
}
for(int j = lower_bound(note[x].begin(), note[x].end(), y) - note[x].begin() + 1; j ; j -= j&-j){
f[x][j - 1] += val;
}
tmp.push_back(x);
}
}
int get(int x, int y){
++y;
int res = 0;
for(; x; x -= x &-x){
if(f[x].empty()){
sort(note[x].begin(), note[x].end());
note[x].erase(unique(note[x].begin(), note[x].end()), note[x].end());
f[x].resize(note[x].size() + 2);
}
for(int j = lower_bound(note[x].begin(), note[x].end(), y) - note[x].begin() + 1; j <= note[x].size(); j += j&-j){
res += f[x][j - 1];
}
}
return res;
}
void clear(){
for(auto p : tmp) f[p].clear(), note[p].clear();
tmp.clear();
}
}con;
vector<ll> one, nen;
int calc( ll val){
return lower_bound(nen.begin(), nen.end(), val) - nen.begin() + 1;
}
void solve(int i){
len = 0;
tmp.clear();
dfs(i, -1);//tìm tplt
for(auto p : tmp) vis[p] = 0;
dfs_2(root);//tạo dis()
int x = root_2;
one.clear();
while(x != root){
one.push_back(x);
x = par[x];
}
one.push_back(root);
reverse(one.begin(), one.end());
//
for(auto p : tmp) vis[p] = 0;
Time = 0;
dfs_3(root, -1);//xây euler tour
for(auto p : tmp) vis[p] = 0;
for(auto p : one) vis[p] = 1;
build(1, 1, Time);
for(auto u : tmp){
if(vis[u]) continue;
for(auto [id, T] : Q[u]){
int l = st[u], r = en[u];
ans[id] = get(1, 1, Time, l, r, T + dis[u]);
}
}
for(auto p : tmp) vis[p] = 0;
dfs_4(root);//xây dos vòng tròn
nen.clear();
for(int i = 1; i <= one.size(); ++i){
int u = one[i - 1];
hos[i].clear();
dfs_5(u, i);
for(auto j : hos[i]){
nen.push_back(dis[j]);
nen.push_back(dis[j] % len);
}
for(auto [id, T] : Q[u]){
nen.push_back(T - dos[u]);
nen.push_back((T - dos[u]) % len);
nen.push_back(T + dis[u]);
nen.push_back((T + dis[u]) % len);
}
}
sort(nen.begin(), nen.end());
nen.erase(unique(nen.begin(), nen.end()), nen.end());
// for(auto p : tmp) vis[p] = 1;
// for(auto p : tmp) cout << p << ' ';
// cout << endl;
for(int i = 1; i <= one.size(); ++i){
int u = one[i - 1];
for(auto [id, T] : Q[u]){
int x = calc( T - dos[u]);
int y = calc((T - dos[u]) % len);
con.Fake_get(x, y);
}
for(auto j : hos[i]){
int x = calc(dis[j]);
int y = calc(dis[j] % len);
con.Fake_update(x, y);
}
}
for(int i = 1; i <= one.size(); ++i){
int u = one[i - 1];
for(auto [id, T] : Q[u]){
int x = calc(T - dos[u]);
int y = calc((T - dos[u]) % len);
ans[id] += ((T - dos[u]) / len) * str[0].get(x);
ans[id] += str[0].get(x);
ans[id] -= str[1].get(x);
ans[id] -= con.get(x, y);
}
for(auto j : hos[i]){
int x = calc(dis[j]);
int y = calc( dis[j] % len);
str[0].update(x, 1);
str[1].update(x, dis[j] / len);
con.update(x, y, 1);
}
}
str[0].clear();str[1].clear();con.clear();
for(int i = 1; i <= one.size(); ++i){
int u = one[i - 1];
for(auto [id, T] : Q[u]){
int x = calc(T + dis[u]);
int y = calc((T + dis[u]) % len);
con.Fake_get(x, y);
}
for(auto j : hos[i]){
int x = calc( dis[j]);
int y = calc(dis[j] % len);
con.Fake_update(x, y);
}
}
for(int i = one.size(); i >= 1; --i){
int u = one[i - 1];
for(auto j : hos[i]){
int x = calc( dis[j]);
int y = calc( dis[j] % len);
str[0].update(x, 1);
str[1].update(x, dis[j] / len);
con.update(x, y, 1);
// cout << j << ' ' << dis[j] << endl;
}
for(auto [id, T] : Q[u]){
int x = calc(T + dis[u]);
int y = calc((T + dis[u]) % len);
ans[id] += ((T + dis[u]) / len) * (str[0].get(x));
ans[id] += str[0].get(x);
// cout << id << ' ' << T + dis[u] << ' ' << str[0].get(x) << endl;
ans[id] -= str[1].get(x);
ans[id] -= con.get(x, y);
}
}
str[0].clear();str[1].clear();con.clear();
// cout << len<<"#"<<endl;
for(auto p : tmp) vis[p] = 1;
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n >> m >> L >> C;
for(int i = 1; i <= n; ++i) cin >> a[i].fi, a[i].se = i;
for(int i = 1; i <= m; ++i) cin >> b[i].fi, b[i].se = i + n;
int q; cin >> q;
for(int i = 1; i <= q; ++i){
cin >> c[i].fi >> c[i].se;
Q[c[i].fi].push_back({i, c[i].se});
}
for(int i = n + 1; i <= 2 * n; ++i){
a[i] = a[i - n];
int l = i - n + 1, r = i, kq = i;
ll cur = L * (C / L) + L;
int x = C % L;
while(l <= r){
int mid = r + l >> 1;
int dist = 0;
if(a[mid].fi > a[i].fi){
dist = L - a[mid].fi + a[i].fi;
}
else dist = a[i].fi - a[mid].fi;
if(dist >= x){
l = mid + 1;
kq = mid;
cur = 1ll * L * (C / L) + dist;
}
else r = mid - 1;
}
if(kq != -1){
// cout << a[i].se << ' ' << a[kq].se << ' ' << cur << endl;
mp[a[i].se][a[kq].se] = cur;
adj[a[i].se].push_back({cur, a[kq].se});
adj[a[kq].se].push_back({cur, a[i].se});
inp[a[i].se].push_back({cur, a[kq].se});
out[a[kq].se].push_back({cur, a[i].se});
}
}
for(int i = 1; i <= m; ++i){
int l = 1, r = n, kq = -1;
while(l <= r){
int mid = r+ l >> 1;
if(a[mid].fi <= b[i].fi){
l = mid + 1;
kq = mid;
}
else r = mid - 1;
}
if(kq != -1){
ll cur = b[i].fi - a[kq].fi;
mp[b[i].se][a[kq].se] = cur;
adj[b[i].se].push_back({cur, a[kq].se});
adj[a[kq].se].push_back({cur, b[i].se});
inp[b[i].se].push_back({cur, a[kq].se});
out[a[kq].se].push_back({cur, b[i].se});
}
else{
kq = n;
ll cur = b[i].fi + (L - a[kq].fi);
mp[b[i].se][a[kq].se] = cur;
adj[b[i].se].push_back({cur, a[kq].se});
adj[a[kq].se].push_back({cur, b[i].se});
inp[b[i].se].push_back({cur, a[kq].se});
out[a[kq].se].push_back({cur, b[i].se});
}
}
for(int i = 1; i <= n; ++i){
if(!vis[i]){
solve(i);
}
}
// cout << dis[4]<< ' ' <<dis[3] << endl;
for(int i = 1; i <= q; ++i) cout << ans[i] <<endl;
}
/*
5 3 20 6
0 4 8 12 16
2 11 14
9
4 1932
2 93787
1 89
5 98124798
1 2684
1 137598
3 2
3 8375
4 237
8 15 217 33608
0 12 71 96 111 128 152 206
4 34 42 67 76 81 85 104 110 117 122 148 166 170 212
14
2 223544052420046341
3 86357593875941375
4 892813012303440034
1 517156961659770735
7 415536186438473633
6 322175014520330760
7 557706040951533058
6 640041274241532527
5 286263974600593111
8 349405886653104871
1 987277313830536091
5 989137777159975413
2 50689028127994215
7 445686748471896881
*/
Compilation message
harvest.cpp: In function 'void build(int, int, int)':
harvest.cpp:84:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
84 | int mid = r + l >> 1;
| ~~^~~
harvest.cpp: In function 'int get(int, int, int, int, int, long long int)':
harvest.cpp:96:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
96 | int mid = r + l >> 1;
| ~~^~~
harvest.cpp: In member function 'int cay3::get(int, int)':
harvest.cpp:173:97: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
173 | for(int j = lower_bound(note[x].begin(), note[x].end(), y) - note[x].begin() + 1; j <= note[x].size(); j += j&-j){
| ~~^~~~~~~~~~~~~~~~~
harvest.cpp: In function 'void solve(int)':
harvest.cpp:223:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
223 | for(int i = 1; i <= one.size(); ++i){
| ~~^~~~~~~~~~~~~
harvest.cpp:243:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
243 | for(int i = 1; i <= one.size(); ++i){
| ~~^~~~~~~~~~~~~
harvest.cpp:256:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
256 | for(int i = 1; i <= one.size(); ++i){
| ~~^~~~~~~~~~~~~
harvest.cpp:275:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
275 | for(int i = 1; i <= one.size(); ++i){
| ~~^~~~~~~~~~~~~
harvest.cpp: At global scope:
harvest.cpp:315:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
315 | main(){
| ^~~~
harvest.cpp: In function 'int main()':
harvest.cpp:334:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
334 | int mid = r + l >> 1;
| ~~^~~
harvest.cpp:359:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
359 | int mid = r+ l >> 1;
| ~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
105 ms |
232528 KB |
Output is correct |
| 2 |
Correct |
118 ms |
233304 KB |
Output is correct |
| 3 |
Correct |
120 ms |
235872 KB |
Output is correct |
| 4 |
Correct |
116 ms |
235468 KB |
Output is correct |
| 5 |
Correct |
111 ms |
235724 KB |
Output is correct |
| 6 |
Correct |
108 ms |
235724 KB |
Output is correct |
| 7 |
Correct |
115 ms |
235724 KB |
Output is correct |
| 8 |
Correct |
106 ms |
235532 KB |
Output is correct |
| 9 |
Correct |
112 ms |
235464 KB |
Output is correct |
| 10 |
Correct |
110 ms |
235360 KB |
Output is correct |
| 11 |
Correct |
117 ms |
235308 KB |
Output is correct |
| 12 |
Correct |
116 ms |
236408 KB |
Output is correct |
| 13 |
Correct |
122 ms |
236728 KB |
Output is correct |
| 14 |
Correct |
116 ms |
234960 KB |
Output is correct |
| 15 |
Correct |
106 ms |
235464 KB |
Output is correct |
| 16 |
Correct |
107 ms |
235628 KB |
Output is correct |
| 17 |
Correct |
104 ms |
235604 KB |
Output is correct |
| 18 |
Correct |
101 ms |
235572 KB |
Output is correct |
| 19 |
Correct |
104 ms |
235540 KB |
Output is correct |
| 20 |
Correct |
111 ms |
235740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1200 ms |
290128 KB |
Output is correct |
| 2 |
Correct |
353 ms |
300992 KB |
Output is correct |
| 3 |
Correct |
285 ms |
292324 KB |
Output is correct |
| 4 |
Correct |
1316 ms |
337004 KB |
Output is correct |
| 5 |
Correct |
319 ms |
320964 KB |
Output is correct |
| 6 |
Correct |
304 ms |
320876 KB |
Output is correct |
| 7 |
Correct |
262 ms |
295548 KB |
Output is correct |
| 8 |
Correct |
257 ms |
295696 KB |
Output is correct |
| 9 |
Correct |
1667 ms |
380320 KB |
Output is correct |
| 10 |
Correct |
1594 ms |
374440 KB |
Output is correct |
| 11 |
Correct |
1863 ms |
382856 KB |
Output is correct |
| 12 |
Correct |
1760 ms |
382928 KB |
Output is correct |
| 13 |
Correct |
1854 ms |
382660 KB |
Output is correct |
| 14 |
Correct |
1608 ms |
377268 KB |
Output is correct |
| 15 |
Correct |
1317 ms |
339312 KB |
Output is correct |
| 16 |
Correct |
308 ms |
309980 KB |
Output is correct |
| 17 |
Correct |
277 ms |
309508 KB |
Output is correct |
| 18 |
Correct |
196 ms |
264004 KB |
Output is correct |
| 19 |
Correct |
190 ms |
264004 KB |
Output is correct |
| 20 |
Correct |
333 ms |
301512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
105 ms |
232528 KB |
Output is correct |
| 2 |
Correct |
118 ms |
233304 KB |
Output is correct |
| 3 |
Correct |
120 ms |
235872 KB |
Output is correct |
| 4 |
Correct |
116 ms |
235468 KB |
Output is correct |
| 5 |
Correct |
111 ms |
235724 KB |
Output is correct |
| 6 |
Correct |
108 ms |
235724 KB |
Output is correct |
| 7 |
Correct |
115 ms |
235724 KB |
Output is correct |
| 8 |
Correct |
106 ms |
235532 KB |
Output is correct |
| 9 |
Correct |
112 ms |
235464 KB |
Output is correct |
| 10 |
Correct |
110 ms |
235360 KB |
Output is correct |
| 11 |
Correct |
117 ms |
235308 KB |
Output is correct |
| 12 |
Correct |
116 ms |
236408 KB |
Output is correct |
| 13 |
Correct |
122 ms |
236728 KB |
Output is correct |
| 14 |
Correct |
116 ms |
234960 KB |
Output is correct |
| 15 |
Correct |
106 ms |
235464 KB |
Output is correct |
| 16 |
Correct |
107 ms |
235628 KB |
Output is correct |
| 17 |
Correct |
104 ms |
235604 KB |
Output is correct |
| 18 |
Correct |
101 ms |
235572 KB |
Output is correct |
| 19 |
Correct |
104 ms |
235540 KB |
Output is correct |
| 20 |
Correct |
111 ms |
235740 KB |
Output is correct |
| 21 |
Correct |
1200 ms |
290128 KB |
Output is correct |
| 22 |
Correct |
353 ms |
300992 KB |
Output is correct |
| 23 |
Correct |
285 ms |
292324 KB |
Output is correct |
| 24 |
Correct |
1316 ms |
337004 KB |
Output is correct |
| 25 |
Correct |
319 ms |
320964 KB |
Output is correct |
| 26 |
Correct |
304 ms |
320876 KB |
Output is correct |
| 27 |
Correct |
262 ms |
295548 KB |
Output is correct |
| 28 |
Correct |
257 ms |
295696 KB |
Output is correct |
| 29 |
Correct |
1667 ms |
380320 KB |
Output is correct |
| 30 |
Correct |
1594 ms |
374440 KB |
Output is correct |
| 31 |
Correct |
1863 ms |
382856 KB |
Output is correct |
| 32 |
Correct |
1760 ms |
382928 KB |
Output is correct |
| 33 |
Correct |
1854 ms |
382660 KB |
Output is correct |
| 34 |
Correct |
1608 ms |
377268 KB |
Output is correct |
| 35 |
Correct |
1317 ms |
339312 KB |
Output is correct |
| 36 |
Correct |
308 ms |
309980 KB |
Output is correct |
| 37 |
Correct |
277 ms |
309508 KB |
Output is correct |
| 38 |
Correct |
196 ms |
264004 KB |
Output is correct |
| 39 |
Correct |
190 ms |
264004 KB |
Output is correct |
| 40 |
Correct |
333 ms |
301512 KB |
Output is correct |
| 41 |
Correct |
1338 ms |
482484 KB |
Output is correct |
| 42 |
Correct |
727 ms |
332520 KB |
Output is correct |
| 43 |
Correct |
1118 ms |
329432 KB |
Output is correct |
| 44 |
Correct |
2035 ms |
509572 KB |
Output is correct |
| 45 |
Correct |
1022 ms |
493952 KB |
Output is correct |
| 46 |
Correct |
1118 ms |
494660 KB |
Output is correct |
| 47 |
Correct |
1233 ms |
496220 KB |
Output is correct |
| 48 |
Correct |
938 ms |
493032 KB |
Output is correct |
| 49 |
Correct |
923 ms |
495480 KB |
Output is correct |
| 50 |
Correct |
971 ms |
476532 KB |
Output is correct |
| 51 |
Correct |
949 ms |
472360 KB |
Output is correct |
| 52 |
Runtime error |
1240 ms |
524288 KB |
Execution killed with signal 9 |
| 53 |
Halted |
0 ms |
0 KB |
- |
