Submission #1106753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106753		Bananabread	Harvest (JOI20_harvest)	C++17	20 / 100	200 ms	79804 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[500001],adjrev[500001];
ll vis[500001];
ll dist[500001];
ll cnt;
vector<vector<pair<ll,ll>>> compart;
vector<vector<ll>> pref;
vector<ll> len;
ll num[500001];
ll insub[500001];
bool inloop[500001];
ll root;
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){
    vis[u]=1;
    num[u]=cnt;
    if(u>n){
        insub[u]=1;
        compart[cnt].push_back({d%len[cnt],d/len[cnt]});
    }
    for(auto [v,w]:adjrev[u]){
        if(v==root) continue;
        //cout<<u<<' '<<v<<' '<<root<<ntr;
        dfs1(v,d+w,u);
        insub[u]+=insub[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;
        //if(i==j) continue;
        ll v=((a[i]-a[pos])%l+l)%l;
        ll cost=(c-v+l-1)/l*l+v;
//        cout<<i<<' '<<pos<<' '<<cost<<ntr;
        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});
//        cout<<i+n<<' '<<v<<' '<<cost<<ntr;
    }
    compart.push_back({});
    pref.push_back({});
    len.push_back(0);
    for(int i=1;i<=m;i++){
        if(vis[i+n]) continue;
        root=0,dfs(i+n);
        cnt++;
        compart.push_back({});
        pref.push_back({});
        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());
        pref[cnt].push_back(compart[cnt][0].second);
        for(int i=1;i<compart[cnt].size();i++){
            pref[cnt].push_back(pref[cnt].back()+compart[cnt][i].second);
        }
    }
//    for(int i=1;i<=n+m;i++){
//        cout<<insub[i]<<' ';
//    }
//    cout<<ntr;
    cin>>q;
    for(int i=1;i<=q;i++){
        ll u,t;
        cin>>u>>t;
        t-=dist[u];
        if(!inloop[u]){
            cout<<insub[u]<<ntr;
            continue;
        }
        else{
            ll ans=insub[u]*(dist[u]>0);
            ll p=t/len[num[u]];
            ll q=t%len[num[u]];
            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+=(compart[num[u]].size())*p-pref[num[u]].back();
            ans+=pos+1;
            cout<<ans<<ntr;
        }

    }
}

Compilation message (stderr)

harvest.cpp: In function 'int main()':
harvest.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int i=1;i<compart[cnt].size();i++){
      |                     ~^~~~~~~~~~~~~~~~~~~~

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