oj.uz

Submission #1000815

# Submission time Handle Problem Language Result Execution time Memory
1000815 2024-06-18T09:35:22 Z Unforgettablepl Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 174204 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 681 ms 173884 KB Output is correct
3 Correct 689 ms 173908 KB Output is correct
4 Correct 714 ms 173864 KB Output is correct
5 Correct 714 ms 173860 KB Output is correct
6 Correct 723 ms 173948 KB Output is correct
7 Correct 716 ms 173904 KB Output is correct
8 Correct 669 ms 173652 KB Output is correct
9 Correct 662 ms 173756 KB Output is correct
10 Correct 665 ms 173864 KB Output is correct
11 Correct 752 ms 173648 KB Output is correct
12 Correct 783 ms 174140 KB Output is correct
13 Correct 855 ms 174204 KB Output is correct
14 Correct 728 ms 173892 KB Output is correct
15 Correct 691 ms 173868 KB Output is correct
16 Correct 700 ms 173908 KB Output is correct
17 Correct 692 ms 173880 KB Output is correct
18 Correct 694 ms 173904 KB Output is correct
19 Correct 714 ms 173872 KB Output is correct
20 Correct 712 ms 173868 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1489 ms 8080 KB Output is correct
2 Execution timed out 5040 ms 19024 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 681 ms 173884 KB Output is correct
3 Correct 689 ms 173908 KB Output is correct
4 Correct 714 ms 173864 KB Output is correct
5 Correct 714 ms 173860 KB Output is correct
6 Correct 723 ms 173948 KB Output is correct
7 Correct 716 ms 173904 KB Output is correct
8 Correct 669 ms 173652 KB Output is correct
9 Correct 662 ms 173756 KB Output is correct
10 Correct 665 ms 173864 KB Output is correct
11 Correct 752 ms 173648 KB Output is correct
12 Correct 783 ms 174140 KB Output is correct
13 Correct 855 ms 174204 KB Output is correct
14 Correct 728 ms 173892 KB Output is correct
15 Correct 691 ms 173868 KB Output is correct
16 Correct 700 ms 173908 KB Output is correct
17 Correct 692 ms 173880 KB Output is correct
18 Correct 694 ms 173904 KB Output is correct
19 Correct 714 ms 173872 KB Output is correct
20 Correct 712 ms 173868 KB Output is correct
21 Correct 1489 ms 8080 KB Output is correct
22 Execution timed out 5040 ms 19024 KB Time limit exceeded
23 Halted 0 ms 0 KB -