Submission #1000815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000815		Unforgettablepl	Harvest (JOI20_harvest)	C++17	5 / 100	5040 ms	174204 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++){
		set<pair<int,int>> dists;
		for(int j=1;j<=n;j++){
			dists.insert({(l+employee[i]-employee[j])%l,j});
		}
		int modded = c%l;
		auto iter = dists.lower_bound({modded,0ll});
		if(iter==dists.end()){
			adj[i] = {i,(c/l)*l + l};
			continue;
		}
		adj[i] = {iter->second,(c/l)*l + iter->first};
	}
	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