Submission #1107595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107595		Bananabread	Harvest (JOI20_harvest)	C++17	100 / 100	303 ms	120024 KiB

harvest

#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname "temp"
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
ll a[200001],b[200001];
ll n,m,l,c,q;
vector<pair<ll,ll>> adj[400001],adjrev[400001];
ll vis[400001];
ll dist[200001];
ll distrev[400001];
ll pos[200001];
ll sz[400001];
ll euler[400001];
ll fenwick[200001];
ll line[200001];
ll ans[200001];
vector<array<ll,3>> sweep;
ll ones[200001];
ll tin;
ll ord;
ll cnt;
vector<vector<pair<ll,ll>>> compart;
vector<ll> st,ed;
vector<ll> len;
ll num[400001];
ll insub[400001];
bool inloop[400001];
ll root;
void update(ll x,ll val){
    for(;x<=n+m;x+=x&-x){
        insub[x]+=val;
    }
}
ll query(ll x){
    ll s=0;
    for(;x>0;x-=x&-x){
        s+=insub[x];
    }
    return s;
}
void upd(ll x,ll val,ll type){
    if(type){
        for(;x<=m;x+=x&-x){
            fenwick[x]+=val;
        }
    }
    else{
        for(;x<=m;x+=x&-x){
            ones[x]+=val;
        }
    }
}
ll get(ll x,ll type){
    ll s=0;
    for(;x;x-=x&-x){
        if(type) s+=fenwick[x];
        else s+=ones[x];
    }
    return s;
}
void dfs(ll u){
    if(root) return ;
    if(vis[u]){
        root=u;
        return ;
    }
    vis[u]=1;
    for(auto [v,w]:adj[u]){
        dfs(v);
    }
}
void dfs1(ll u=root,ll d=0,ll par=0){
    distrev[u]=d;
    vis[u]=1;
    sz[u]=1;
    euler[u]=++tin;
    num[u]=cnt;
    if(u>n){
        compart[cnt].push_back({d%len[cnt],u-n});
        line[u-n]=d/len[cnt];
    }
    for(auto [v,w]:adjrev[u]){
        if(v==root) continue;
        dfs1(v,d+w,u);
        sz[u]+=sz[v];
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //frep;
    cin>>n>>m>>l>>c;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    for(int i=1;i<=n;i++){
        ll t=((a[i]-c)%l+l)%l;
        ll pos=upper_bound(a+1,a+n+1,t)-a-1;
        if(pos==0) pos=n;
        ll v=((a[i]-a[pos])%l+l)%l;
        ll cost=(c-v+l-1)/l*l+v;
        adj[i].push_back({pos,cost});
        adjrev[pos].push_back({i,cost});
    }
    for(int i=1;i<=m;i++){
        ll v=upper_bound(a+1,a+n+1,b[i])-a-1;
        if(v==0) v=n;
        ll cost=((b[i]-a[v])%l+l)%l;
        adj[i+n].push_back({v,cost});
        adjrev[v].push_back({i+n,cost});
    }
    compart.push_back({});
    len.push_back(0);
    st.push_back(-1);
    ed.push_back(-1);
    for(int i=1;i<=m;i++){
        if(vis[i+n]) continue;
        root=0,dfs(i+n);
        cnt++;
        compart.push_back({});
        st.push_back(1e18);
        ed.push_back(0);
        ll p=root;
        dist[root]=0;
        while(true){
            inloop[p]=1;
            auto [v,w]=adj[p][0];
            if(v==root){
                len.push_back(dist[p]+w);
                break;
            }
            dist[v]=dist[p]+w;
            p=v;
        }
        dfs1();
        sort(compart[cnt].begin(),compart[cnt].end());
        for(auto i:compart[cnt]){
            pos[i.second]=++ord;
            st[cnt]=min(st[cnt],ord);
            ed[cnt]=max(ed[cnt],ord);
        }
    }
    for(int i=1;i<=m;i++){
        sweep.push_back({distrev[i+n],0,i});
    }
//    for(int i=1;i<=n+m;i++) cout<<euler[i]<<' ';
//    cout<<ntr;
    cin>>q;
    for(int i=1;i<=q;i++){
        ll u,t;
        cin>>u>>t;
        sweep.push_back({t+distrev[u],u+1,i});
    }
    sort(sweep.begin(),sweep.end());
    for(auto i:sweep){
//        cout<<i[0]<<' '<<i[1]<<' '<<i[2]<<ntr;
        if(i[1]==0){
            upd(pos[i[2]],line[i[2]],1);
            upd(pos[i[2]],1,0);
            update(euler[i[2]+n],1);
//            cout<<euler[i[2]+n]<<ntr;
//            for(int i=1;i<=n+m;i++){
//                cout<<query(i)<<' ';
//            }
//            cout<<ntr;
        }
        else{
            ll u=i[1]-1;
            ll t=i[0]-distrev[u];
            t-=dist[u];
            ll id=i[2];
            if(!inloop[u]){
                ans[id]=query(euler[u]+sz[u]-1)-query(euler[u]-1);
            }
            else{
                ans[id]+=(query(euler[u]+sz[u]-1)-query(euler[u]-1))*(dist[u]>0);
//                cout<<ans[id]<<ntr;
//                cout<<euler[u]+sz[u]-1<<' '<<euler[u]-1<<ntr;
                ll p=t/len[num[u]];
                ll q=t%len[num[u]];
//                cout<<t<<' '<<p<<' '<<q<<ntr;
                ll lo=0,hi=compart[num[u]].size()-1,pos=-1;
                while(lo<=hi){
                    ll mid=(lo+hi)/2;
                    if(compart[num[u]][mid].first<=q) pos=mid,lo=mid+1;
                    else hi=mid-1;
                }
                ans[id]+=(get(ed[num[u]],0)-get(st[num[u]]-1,0))*p-(get(ed[num[u]],1)-get(st[num[u]]-1,1));
                //cout<<ans[id]<<ntr;
//                cout<<(get(ed[num[u]],0)-get(st[num[u]]-1,0))<<' '<<(get(ed[num[u]],1)-get(st[num[u]]-1,1))<<ntr;
                if(pos>=0){
                    ans[id]+=get(st[num[u]]+pos,0)-get(st[num[u]]-1,0);
//                    cout<<get(st[num[u]]+pos,0)-get(st[num[u]]-1,0)<<ntr;
                }
            }
        }
    }
    for(int i=1;i<=q;i++){
        cout<<ans[i]<<ntr;
    }
}

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