Submission #876194

#	Time	Username	Problem	Language	Result	Execution time	Memory
876194		winter0101	Harvest (JOI20_harvest)	C++14	100 / 100	2198 ms	320440 KiB

harvest

#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]);
}
//
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';
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 75 / 75