Submission #1089735

#TimeUsernameProblemLanguageResultExecution timeMemory
1089735phongHarvest (JOI20_harvest)C++17
25 / 100
2035 ms524288 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...