Submission #1006046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006046		Unforgettablepl	Harvest (JOI20_harvest)	C++17	5 / 100	1431 ms	524288 KiB

harvest

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int INF = 1e18;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,l,c;
    cin >> n >> m >> l >> c;
    vector<int> employee(n+1);
    vector<int> apple(m);
    vector<pair<int,int>> adj(n+1);
    for(int i=1;i<=n;i++)cin>>employee[i];
    for(int&i:apple)cin>>i;
    for(int i=1;i<=n;i++){
        int modded = c%l;
        int iter = 0;
        for(int jump=131072;jump;jump/=2){
            if(iter+jump>n)continue;
            if((l+employee[i]-employee[(n-iter-jump+i)%n +1])%l < modded)iter+=jump;
        }
        iter++;
        if(iter==n+1){
            adj[i] = {i,(c/l)*l + l};
            continue;
        }
        adj[i] = {(n-iter+i)%n +1,(c/l)*l + (l+employee[i]-employee[(n-iter+i)%n +1])%l};
    }
    vector<vector<pair<int,int>>> eqn(n+1);
    for(int&i:apple){
        int start = -1;
        if(i<employee[1])start = n;
        else {
            start = upper_bound(employee.begin()+1,employee.end(),i)-employee.begin()-1;
        }
        vector<pair<int,int>> curr(n+1,{INF,INF});
        function<void (int,int)> dfs = [&](int x,int tim){
            if(curr[x].second!=INF)return;
            if(curr[x].first!=INF)curr[x].second=tim-curr[x].first;
            else curr[x].first = tim;
            dfs(adj[x].first,tim+adj[x].second);
        };
        dfs(start,(l+i-employee[start])%l);
        for(int i=1;i<=n;i++)eqn[i].emplace_back(curr[i]);
    }
    int q;
    cin >> q;
    for(int i=1;i<=q;i++){
        int v,t;
        cin >> v >> t;
        int ans = 0;
        for(auto[a,b]:eqn[v]){
            if(t<a)continue;
            ans+=(t-a)/b + 1;
        }
        cout << ans << '\n';
    }
}

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