This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=998244353,mxn=4e5+5,inf=1e18,minf=-1e18,lg=30;
//#undef int
int n,k,m,q,c,l;
void setIO(string name){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
int pos[mxn+10],post[mxn+10],pref[mxn+10];
int caldist(int from,int go){
if(from>go)return from-go;
return l-go+from;
}
vector<pii>adj[mxn+10];
void addedge(int x,int y,int z){
adj[x].pb({y,z});
}
int on[mxn+10],vis[mxn+10],oncycle[mxn+10]; //on cycle
int dist[mxn+10],sz[mxn+10],tin[mxn+10],tout[mxn+10],who[mxn+10],where[mxn+10];
int compsz[mxn+10];
vector<int>cycle[mxn+10];
int T=n,cnt=0;
stack<int>st;
void getcycle(int cur){
if(vis[cur])return;
vis[cur]=on[cur]=1;
st.push(cur);
for(auto i:adj[cur]){
if(on[i.f]){
cnt++;
cycle[cnt].pb(i.f),oncycle[i.f]=cnt;
while(st.top()!=i.f)cycle[cnt].pb(st.top()),oncycle[st.top()]=cnt,st.pop();
reverse(all(cycle[cnt]));
compsz[cnt]=dist[cur]-dist[i.f]+i.s;
}
if(!vis[i.f]){
dist[i.f]=dist[cur]+i.s;
getcycle(i.f);
}
}
on[cur]=0;
if(!st.empty())st.pop();
}
int curtime=0;
pii cant;
void getdist(int cur){
sz[cur]=1;
tin[cur]=++curtime;
who[tin[cur]]=cur;
for(auto i:adj[cur])if(cant.f!=cur||cant.s!=i.f){
dist[i.f]=dist[cur]+i.s;
getdist(i.f);
sz[cur]+=sz[i.f];
}
tout[cur]=curtime;
}
vector<pii>qry[mxn+10];
int ans[mxn+10];
struct fen{
int fwk[mxn+10],sz=0;
vector<pii>keep;
void update(int pos,int val){
pos++;
keep.pb({pos,val});
for(int i=pos;i<=sz;i+=(i&-i))fwk[i]+=val;
}
int qry(int pos){
int sum=0;
pos++;
pos=min(pos,sz);
for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i];
return sum;
}
void re(){
for(auto i:keep)for(int j=i.f;j<=sz;j+=(j&-j))fwk[j]-=i.s;
keep.clear();
}
}t,t2;
/*
sack
*/
vector<int>have[mxn+10];
vector<int>comp;
vector<pii>extra[mxn+10];
int cc=0;
void sack(int cur,int keep){
//solving case where node is not on cycle
int hvy=0;
vis[cur]=1;
for(auto i:adj[cur])if(cur!=cant.f||i.f!=cant.s){
if(sz[i.f]>sz[hvy])hvy=i.f;
}
for(auto i:adj[cur])if((cur!=cant.f||i.f!=cant.s)&&i.f!=hvy)sack(i.f,0);
if(hvy)sack(hvy,1);
int x=0;
for(auto i:adj[cur])if(cur!=cant.f||i.f!=cant.s){
if(i.f!=hvy)for(int j=tin[i.f];j<=tout[i.f];j++)if(who[j]>n)t.update(where[who[j]],1);
if(have[i.f].size()>have[cur].size())swap(have[cur],have[i.f]);
for(auto j:have[i.f])have[cur].pb(j);
}
if(cur>n)t.update(where[cur],1),have[cur].pb(dist[cur]),sz[cur]=1;
for(auto i:qry[cur]){
auto it=upper_bound(all(comp),i.f+dist[cur])-comp.begin()-1;
if(it)ans[i.s]=t.qry(it);
}
if(!keep)t.re();
}
/*
*/
int32_t main(){
fastio
cin>>n>>m>>l>>c;
for(int i=1;i<=n;i++)cin>>pos[i];
for(int i=1;i<=m;i++)cin>>post[i];
int cur=1;
k=c/l;
c%=l;
for(int i=n+1;i<=2*n;i++)pos[i]=pos[i-n]+l;
for(int i=n+1;i<=2*n;i++){
while(cur<=i&&pos[i]-pos[cur]>=c)cur++;
addedge(cur-1-((cur-1>n)?n:0),i-n,pos[i]-pos[cur-1]+(k*l));
}
T=n;
for(int i=1;i<=n;i++)if(!vis[i])getcycle(i);
cur=1;
for(int i=1;i<=m;i++){
T++;
while(cur<=n&&post[i]>pos[cur])cur++;
pos[T]=post[i];
if(cur==1)addedge(n,T,caldist(pos[T],pos[n]));
else addedge(cur-1,T,caldist(pos[T],pos[cur-1]));
}
for(int i=1;i<=cnt;i++){
cant={cycle[i].back(),cycle[i][0]};
dist[cycle[i][0]]=0;
getdist(cycle[i][0]);
}
for(int i=1;i<=T;i++)comp.pb(dist[i]),vis[i]=0;
sort(all(comp));
comp.erase(unique(all(comp)),comp.end());
t.sz=comp.size();
for(int i=n+1;i<=T;i++)where[i]=lb(all(comp),dist[i])-comp.begin();
cin>>q;
for(int i=0;i<q;i++){
int v,t;cin>>v>>t;
qry[v].pb({t,i});
}
for(int i=1;i<=cnt;i++){
cc=i;
cant={cycle[i].back(),cycle[i][0]};
sack(cycle[i][0],0);
t.re();
}
vector<pair<pii,int>>qry2;
for(int i=1;i<=cnt;i++){
int head=cycle[i][0];
for(auto j:cycle[i])for(auto k:qry[j])qry2.pb({{k.f,j},k.s});
sort(all(qry2));
int sum=0;
comp.clear();
for(auto j:have[head])comp.pb(j%compsz[i]);
for(auto j:qry2)comp.pb(j.f.f%compsz[i]);
sort(all(have[head]));
cur=0;
sort(all(comp));
comp.erase(unique(all(comp)),comp.end());
t.sz=comp.size();
for(auto j:qry2){
while(cur<have[head].size()&&j.f.f>=have[head][cur]){
t.update(lb(all(comp),have[head][cur]%compsz[i])-comp.begin(),1);
sum+=(have[head][cur])/compsz[i];
cur++;
}
ans[j.s]+=((j.f.f/compsz[i])*cur)-sum+t.qry(lb(all(comp),j.f.f%compsz[i])-comp.begin())-cur;
int val=(j.f.f%compsz[i])-compsz[i]+dist[j.f.s];
int pos=upper_bound(all(comp),val)-comp.begin()-1;
if(pos>=0)ans[j.s]+=t.qry(pos);
val+=compsz[i];
pos=upper_bound(all(comp),val)-comp.begin()-1;
if(pos>=0)ans[j.s]+=t.qry(pos)-t.qry(lb(all(comp),j.f.f%compsz[i])-comp.begin());
}
t.re();
qry2.clear();
}
for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
}
/*
create weighted directed graph with cycle on top
a tree will attach to the first node that harvest it with cost of dist
tree will move along the graph. we just need to find how many times a tree passes a given node and time
for qry v,T;
if node v is not in the cycle we can just find the number of tree in the subtree where dist(tree,v)<=T
can use sack on this
else the node v is on the cycle on top
let sz=size of the cycle
we can compute the first node treei will reach in the cycle. let the node be sti
then the time left for tree to move is T-dist(sti,treei)-dist(sti,v) = xi
Ti=dist(sti,treei)+dist(sti,v)
then we just need to find the sum of floor[xi/sz]?
floor[T-dist/sz] counting the first visit
floor[t-dist/sz]= floor[T/sz]-floor[dist/sz] - 1 +(1 if T mod sz>= dist mod sz)
group the node at node g
find all node affected when an apple move from sti->g
then add contribution for how many laps can the apple move starting from returning to g
then the apple may still able to move a little which will affect node V iff (T-Ti)%sz>=sz-dist(sti,g)
2 cases
T%sz >= Ti %sz
T%sz-Ti%sz>=sz-dist(sti,g)
T%sz-sz+dist(sti,g)>=Ti%sz
then qry all Ti%sz
if T%sz< Ti%sz
T%sz-Ti%sz+sz>=sz-dist(sti,g)
T%sz+dist(sti,g)>=Ti%sz
qry all Ti%sz in range (T%sz,T%sz+dist(sti,g))
*/
Compilation message (stderr)
harvest.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
32 | #pragma GCC optimize ("03,unroll-lopps")
| ^
harvest.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
38 | void setIO(string name){
| ^
harvest.cpp:44:28: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
44 | int caldist(int from,int go){
| ^
harvest.cpp:49:31: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
49 | void addedge(int x,int y,int z){
| ^
harvest.cpp:58:22: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
58 | void getcycle(int cur){
| ^
harvest.cpp:81:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
81 | void getdist(int cur){
| ^
harvest.cpp:97:32: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
97 | void update(int pos,int val){
| ^
harvest.cpp:102:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
102 | int qry(int pos){
| ^
harvest.cpp:109:13: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
109 | void re(){
| ^
harvest.cpp:121:27: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
121 | void sack(int cur,int keep){
| ^
harvest.cpp: In function 'void sack(long long int, long long int)':
harvest.cpp:130:9: warning: unused variable 'x' [-Wunused-variable]
130 | int x=0;
| ^
harvest.cpp: At global scope:
harvest.cpp:145:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
145 | int32_t main(){
| ^
harvest.cpp: In function 'int32_t main()':
harvest.cpp:204:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
204 | while(cur<have[head].size()&&j.f.f>=have[head][cur]){
| ~~~^~~~~~~~~~~~~~~~~~
harvest.cpp: In function 'void setIO(std::string)':
harvest.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
