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<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
const int maxn=2e5+9;
int a[maxn],b[maxn];
struct BIT{
vector<long long>bit;
int n;
void resz(int _n){
n=_n;
bit.clear();
bit.resize(n+1);
for1(i,1,n)bit[i]=0;
}
void add(int pos,long long val){
for(;pos<=n;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
void del(int pos){
for (;pos<=n;pos+=(pos-(pos&(pos-1))))bit[pos]=0;
}
long long get(int pos){
long long sum=0;
if (pos<0)return 0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos];
return sum;
}
long long get(int l,int r){
if (l>r)return 0;
return get(r)-get(l-1);
}
};
int id[maxn*2];
#define pil pair<int,long long>
vector<pil>g[maxn*2];//edge
int gr[maxn];//group of cycle
int deg[maxn*2];//deg to remove
bool vis[maxn];//travel in cycle
long long dep[maxn];//dep in cycle
int num=0;
vector<int>cc[maxn];//vertice in each cycle
long long len[maxn];
long long dfs(int u){//dfs cycle
gr[u]=num;
cc[num].pb(u);
long long ans=0;
vis[u]=1;
for (auto v:g[u]){
ans+=v.se;
if (!vis[v.fi]){
vis[v.fi]=1;
dep[v.fi]=dep[u]+v.se;
ans+=dfs(v.fi);
}
}
return ans;
}
vector<pil>rg[maxn*2];//reverse edge
long long d[maxn*2];//dep in tree
vector<pil>h[maxn*2];//apple
int in[maxn*2],out[maxn*2];
int rootincyc[maxn*2];
int tme=0;
pil query[maxn];
int n,m;
void redfs(int u,int root){
if (u>n)h[root].pb({u,d[u]});
rootincyc[u]=root;
in[u]=++tme;
for (auto v:rg[u]){
if (deg[v.fi])continue;
d[v.fi]=d[u]+v.se;
redfs(v.fi,root);
}
out[u]=tme;
}
struct line{
int type;//update or answer
int u;//type of apple of vertice
long long val;//time of dep
int idx;
bool operator < (const line &p)const {
if (val==p.val)return type<p.type;
return val<p.val;
}
};
struct queryt2{
int u;
long long k;
int id;
};
vector<line>quest[maxn];
vector<queryt2>quet[maxn];
long long cum(int u,int v){
if (dep[v]>=dep[u])return dep[v]-dep[u];
return len[gr[u]]-(dep[u]-dep[v]);
}
long long answer[maxn];
//solve for cycle
long long du;
long long value[maxn*2];
long long value_mod[maxn*2];
int pos[maxn];
int revpos[maxn*2];
vector<int>arr[maxn*4];
BIT cnt[maxn*4];
BIT st[maxn*4];
int pos_update[maxn*2][20];
int dep_tree[maxn*4];
void build(int id,int l,int r){
arr[id].clear();
arr[id].resize(r-l+1+1),st[id].resz(r-l+1),cnt[id].resz(r-l+1);
int dd=dep_tree[id];
for1(i,1,r-l+1){
arr[id][i]=pos[i+l-1];
}
sort(arr[id].begin()+1,arr[id].begin()+1+r-l+1,[](int i,int j){
return value[i]<value[j];
});
for1(i,1,r-l+1)pos_update[arr[id][i]][dd]=i;
if (l==r)return;
int mid=(l+r)/2;
dep_tree[id*2]=dep_tree[id*2+1]=dep_tree[id]+1;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
void update(int id,int l,int r,int u){
if (revpos[u]<l||revpos[u]>r)return;
long long val=(value[u]-value_mod[u])/du;
int dd=dep_tree[id];
st[id].add(pos_update[u][dd],val);
cnt[id].add(pos_update[u][dd],1);
if (l==r)return;
int mid=(l+r)/2;
update(id*2,l,mid,u);
update(id*2+1,mid+1,r,u);
}
long long get(int id,int l,int r,int u,int v,long long val,bool fl){
if (l>v||r<u||u>v)return 0;
if (u<=l&&r<=v){
int l1=1,r1=r-l+1,as=-1;
while (l1<=r1){
int mid=(l1+r1)/2;
if (value[arr[id][mid]]<=val){
as=mid;
l1=mid+1;
}
else r1=mid-1;
}
if (as==-1)return 0;
long long nval=((val%du)+du)%du;
long long mval=(val-nval)/du;
long long xxx=cnt[id].get(as);
return xxx*mval-st[id].get(as)+fl*xxx;
}
int mid=(l+r)/2;
return get(id*2,l,mid,u,v,val,fl)+get(id*2+1,mid+1,r,u,v,val,fl);
}
long long l,c;
long long cal(int i,int j){
if (a[j]>=a[i])return a[j]-a[i];
else return l-(a[i]-a[j]);
}
//
/*
Nhan xet: dung duoc do thi mat troi n+m dinh n+m canh
voi nhung dinh khong thuoc chu trinh thi co the tinh bang sweepline
voi nhung dinh thuoc chu trinh, ta co
goi h[u] la nhung qua tao trong cay u
d[u] la do sau cua 1 thang trong cay
dep[u] la do sau cua 1 dinh trong chu trinh voi viec chon dinh nao do thuoc chu trinh lam goc
thi de tinh cac dinh ma thuoc cycle
goi dinh do la x va thoi gian la k
length la do dai chu trinh
ta se can dem tong (v la apple thuoc chu trinh, d[v]<=k,v la con cua u) (k-d[v])/length+[(k-d[v])%length>=d(u,x)] (d(u,x) la khoang cach tu u den x tren chu trinh)
voi subtask 2 thi khong can quan tam k-d[v] vi k>=1e15 nen co the giai trong nlog^2
subtask 3 neu tiep tuc lam the thi se mat nlog^3
nen ta can co nhan xet (k-d[v])/length+[(k-d[v])%length>=d(u,x)]=((k-d[v]-d(u,x))/length+1)*[k-d[v]-d(u,x)>=0]
chung minh
0<=d(u,x)<length
luu y cac phep chia nay la phep lam tron xuong
neu k-d[v]>0 k-d[v]<d(u,x) thi (k-d[v])/length=0
nen luon can k-d[v]>=d(u,x)
goi p=k-d[v] mod length, q=d(u,x) mod length,p1=k-d[v],q1=d(u,x)
neu p>=q thi (p1-q1)/length thoa man vi p1/length=(p1-q1)/length va p1>=q1
neu p<q thi (p1-q1)/length=(p1/length-1) va tuong tu ta lai thoa man
nen ta co the dua ve tinh tong ((k-d[v]-d(u,x))/length+1)*[k-d[v]-d(u,x)>=0] de kiem soat d(u,x) ta co the sweepline u 2 lan, luu 1 cay segmentree,
moi node la bit quan li cac phan tu tu l->r, segment tree quan li theo modulo va moi node sort theo value tu do dua dpt ve nlog^2
*/
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("temp.INP","r",stdin);
//freopen("temp.OUT","w",stdout);
cin>>n>>m>>l>>c;
for1(i,1,n)cin>>a[i];
for1(i,1,n)id[i]=i;
for1(i,n+1,2*n)id[i]=id[i-n];
for1(i,1,n){
long long w=(c/l)*l;
int l1=i+1,r1=i+n,ans=-1;
while (l1<=r1){
int mid=(l1+r1)/2;
if (cal(id[mid],i)>=(c%l)){
ans=mid;
l1=mid+1;
}
else r1=mid-1;
}
if (ans==-1)w+=l,ans=i;
else w+=cal(id[ans],i);
g[i].pb({id[ans], w});
deg[id[ans]]++;
}
for1(i,1,m){
cin>>b[i];
int l1=1,r1=n,ans=n;
while (l1<=r1){
int mid=(l1+r1)/2;
if (a[mid]<=b[i]){
ans=mid;
l1=mid+1;
}
else r1=mid-1;
}
if (a[ans]<=b[i])g[i+n].pb({ans,b[i]-a[ans]});
else g[i+n].pb({ans,l-(a[ans]-b[i])});
}
queue<int>t;
for1(i,1,n){
if (!deg[i]){
t.push(i);
}
}
while (!t.empty()){
auto u=t.front();
t.pop();
for (auto v:g[u]){
deg[v.fi]--;
if (!deg[v.fi]){
t.push(v.fi);
}
}
}
vector<long long>cyc;
num=0;
for1(i,1,n){
if (!deg[i]||vis[i])continue;
//detect cycle
num++;
len[num]=dfs(i);
}
for1(i,1,n+m){
for (auto v:g[i]){
rg[v.fi].pb({i,v.se});
}
}
for1(i,1,n){
if (deg[i]){
redfs(i,i);
}
}
int q;
cin>>q;
for1(i,1,q){
cin>>query[i].fi>>query[i].se;
if (!deg[query[i].fi]){
quest[rootincyc[query[i].fi]].pb({2,query[i].fi,query[i].se+d[query[i].fi],i});
}
else {
quet[query[i].fi].pb({query[i].fi,query[i].se,i});
}
}
BIT bit;
bit.resz(n+m);
for1(i,1,n){
if (deg[i]){
vector<line>sol;
for (auto v:h[i]){
sol.pb({1,v.fi,v.se,0});
}
for (auto v:quest[i]){
sol.pb(v);
}
vector<line>().swap(quest[i]);
sort(all(sol));
for (auto v:sol){
if (v.type==1){
bit.add(in[v.u],1);
}
else {
answer[v.idx]=bit.get(in[v.u],out[v.u]);
}
}
for (auto v:sol){
if (v.type==1)bit.del(in[v.u]);
}
}
}
//d dep in tree
//dep dep in cycle
for1(i,1,num){
du=len[i];
int nlen=0;
for(auto u:cc[i]){
for (auto v:h[u]){
value[v.fi]=(v.se-dep[u]);
value_mod[v.fi]=((value[v.fi]%du)+du)%du;
pos[++nlen]=v.fi;
}
}
if (nlen==0)continue;
sort(pos+1,pos+nlen+1,[](int x,int y){
return value_mod[x]<value_mod[y];
});
for1(j,1,nlen){
revpos[pos[j]]=j;
}
build(1,1,nlen);
for(auto u:cc[i]){
for (auto v:h[u])update(1,1,nlen,v.fi);
for (auto v:quet[u]){
int l1=1,r1=nlen,p=0;
long long val=v.k-dep[v.u];
long long nval=((val%du)+du)%du;
while (l1<=r1){
int mid=(l1+r1)/2;
if (value_mod[pos[mid]]<=nval){
p=mid;
l1=mid+1;
}
else r1=mid-1;
}
answer[v.id]+=get(1,1,nlen,1,p,val,1)+get(1,1,nlen,p+1,nlen,val,0);
}
}
nlen=0;
for(auto u:cc[i]){
for (auto v:h[u]){
value[v.fi]=(v.se-dep[u]);
value_mod[v.fi]=((value[v.fi]%du)+du)%du;
pos[++nlen]=v.fi;
}
}
sort(pos+1,pos+nlen+1,[](int x,int y){
return value_mod[x]<value_mod[y];
});
for1(j,1,nlen){
revpos[pos[j]]=j;
}
build(1,1,nlen);
reverse(all(cc[i]));
for(auto u:cc[i]){
for (auto v:quet[u]){
int l1=1,r1=nlen,p=0;
long long val=v.k-dep[v.u]-len[i];
long long nval=((val%du)+du)%du;
while (l1<=r1){
int mid=(l1+r1)/2;
if (value_mod[pos[mid]]<=nval){
p=mid;
l1=mid+1;
}
else r1=mid-1;
}
answer[v.id]+=get(1,1,nlen,1,p,val,1)+get(1,1,nlen,p+1,nlen,val,0);
}
for (auto v:h[u]){
update(1,1,nlen,v.fi);
}
}
}
//
for1(i,1,q){
if (!deg[query[i].fi])cout<<answer[i]<<'\n';
else cout<<answer[i]<<'\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |