Submission #432207

#TimeUsernameProblemLanguageResultExecution timeMemory
432207oolimryHarvest (JOI20_harvest)C++17
100 / 100
1561 ms212340 KiB
#include <bits/stdc++.h> using namespace std; #define sz(x) (int) (x).size() #define all(x) (x).begin(), (x).end() #define show(x) cerr << #x << " is " << x << endl; #define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl; #define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl; #define tern(cond, a, b) (cond ? a : b) typedef long long lint; typedef pair<lint,lint> ii; lint n, m, L, T; const int BUFF = 250000; const int ROOT = 500000; vector<lint> person; lint apple[500005]; lint point[500005]; bool vis[500005]; inline lint getdis(int i){ lint dis = person[i%BUFF] - person[point[i%BUFF]%BUFF]; if(dis < T){ dis += (T/L)*L; } while(dis < T) dis += L; return dis; } lint inf = 1e18 + 1e17; map<lint,lint> infs; vector<ii> adj[500005]; lint cyclesz[500005]; lint dis[500005]; lint low[500005]; lint high[500005]; lint maxval[500005]; lint total[500005]; lint rep[500005]; struct query{ lint u, t, id, ans; }; vector<query> queries; vector<lint> stuff[500005]; lint toinf[500005]; lint sumreps[500005]; vector<lint> allreps; vector<lint> mods[500005]; lint ppcnt = 0; void dfs(lint u, int p = -1){ low[u] = high[u] = ppcnt++; for(ii e : adj[u]){ lint v = e.first, w = e.second; if(v == p) continue; dis[v] = dis[u] + w; if(u == ROOT){ rep[v] = v; allreps.push_back(v); } else rep[v] = rep[u]; dfs(v, u); high[u] = max(high[u], high[v]); } } void dfs2(lint u, int p = -1){ for(ii e : adj[u]){ lint v = e.first; if(v == p) continue; dfs2(v, u); maxval[u] = max(maxval[u], maxval[v]); total[u] += total[v]; } } const int N = (1<<19); vector<lint> tree[2*N]; inline void addshit(int u, lint t){ t += dis[u]; //show2(u, t); maxval[u] = max(maxval[u], t); stuff[rep[u]].push_back(t); total[u]++; for(int i = low[u] + N;i > 0;i >>= 1) tree[i].push_back(t); } inline void getready(){ for(int i = 0;i < 2*N;i++) sort(all(tree[i])); } inline lint get(vector<lint> &v, lint t){ return (lint)(upper_bound(all(v), t) - v.begin()); } inline lint shitquery(int u, lint t){ lint res = 0; for(int l = low[u]+N, r = high[u]+N+1;l < r;l >>= 1, r >>= 1){ if(l&1) res += get(tree[l++], t); if(r&1) res += get(tree[--r], t); } return res; } vector<lint> disshit; inline int getshit1(lint i){ int pos = lower_bound(all(disshit), i) - disshit.begin() + 1; assert(i == disshit[pos-1]); return pos; } vector<lint> history; lint ft[1400005]; inline void unshitupdate(lint i){ i = getshit1(i); if(i == 0) return; history.push_back(i); for(;i <= 1400001;i += i&(-i)){ ft[i]++; } } inline lint unshitquery(lint i){ i = getshit1(i); int res = 0; for(;i > 0;i -= i&(-i)) res += ft[i]; return res; } inline void undoall(){ while(not history.empty()){ int i = history.back(); history.pop_back(); if(i == 0) continue; for(;i <= 1400001;i += i&(-i)){ ft[i] = 0; } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); memset(point, -1, sizeof(point)); cin >> n >> m >> L >> T; person.resize(n); for(int i = 0;i < n;i++) cin >> person[i]; for(int i = 0;i < m;i++) cin >> apple[i]; for(int i = 0;i < n;i++){ auto it = upper_bound(all(person), person[i] - (T%L)); if(it == person.begin()) it = upper_bound(all(person), person[i] - (T%L) + L); it--; point[i] = it - person.begin(); point[i+BUFF] = point[i]+BUFF; } for(int i = 0;i < n;i++){ set<int> cur; int u = i; int cycle = -1; while(true){ if(cur.find(u) != cur.end()) cycle = u; cur.insert(u); if(vis[u]) break; vis[u] = true; u = point[u]; } if(cycle == -1) continue; lint totaldis = 0; u = cycle; vector<int> nodes; while(true){ nodes.push_back(u); totaldis += getdis(u); u = point[u]; if(u == cycle) break; } for(int x : nodes){ cyclesz[x] = totaldis; cyclesz[x+BUFF] = totaldis; } point[cycle] += BUFF; point[cycle+BUFF] = ROOT; } for(int i = 0;i <= ROOT;i++){ if(point[i] == -1) continue; if(point[i] == ROOT) adj[ROOT].push_back(ii(i, 0)); else{ lint dis = getdis(i); adj[point[i]].push_back(ii(i, dis)); } } dfs(ROOT); for(int i = 0;i < m;i++){ auto it = lower_bound(all(person), apple[i]); if(it == person.begin()) it = person.end(); it--; int x = it - person.begin(); lint t = apple[i] - person[x]; if(t < 0) t += L; addshit(x, t); } getready(); dfs2(ROOT); for(lint r : allreps){ //show(r); for(lint x : stuff[r]){ lint MM = cyclesz[r]; lint I = inf; I /= MM; I *= MM; infs[MM] = I; disshit.push_back(x % MM); lint hm = (I-x)/MM + 1; sumreps[r] += hm; //show(hm); mods[r].push_back(x%MM); } sort(all(mods[r])); sort(all(stuff[r])); } //show(inf); int Q; cin >> Q; for(int q = 0;q < Q;q++){ lint u, t; cin >> u >> t; u--; queries.push_back({u,t,q,0}); if(cyclesz[u+BUFF] != 0){ lint r = rep[u+BUFF]; lint MM = cyclesz[r]; disshit.push_back((t+dis[u+BUFF])%MM); } } sort(all(disshit)); disshit.erase(unique(all(disshit)), disshit.end()); sort(all(queries), [&](query a, query b){ if(rep[a.u] == rep[b.u]) return a.t < b.t; else return rep[a.u] < rep[b.u]; }); lint prevrep = -1; lint sumofshit = 0; lint shitcnt = 0; int ptr = 0; for(query &q : queries){ lint u = q.u, t = q.t; lint ans = 0; if(rep[u] != prevrep){ prevrep = rep[u]; undoall(); sumofshit = 0; shitcnt = 0; ptr = 0; } ans += shitquery(u, t+dis[u]); if(cyclesz[u+BUFF] != 0){ t += dis[u+BUFF]; lint r = rep[u+BUFF]; lint MM = cyclesz[r]; while(ptr < sz(stuff[r])){ if(stuff[r][ptr] > t) break; else{ sumofshit += (infs[MM]-stuff[r][ptr])/MM + 1; //shitmods.push_back(stuff[r][ptr] % MM); ///change this unshitupdate(stuff[r][ptr] % MM); ptr++; shitcnt++; } //sort(all(shitmods)); } ans += sumofshit; lint fulls = (infs[MM]-(t+1))/MM; fulls *= shitcnt; if(fulls >= 0){ ans -= fulls; ans -= (shitcnt - unshitquery(t%MM)); ///change this } } q.ans = ans; } sort(all(queries), [&](query a, query b){ return a.id < b.id; }); for(query q : queries) cout << q.ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...