oj.uz

Submission #260944

# Submission time Handle Problem Language Result Execution time Memory
260944 2020-08-11T08:21:39 Z 임성재(#5066) Harvest (JOI20_harvest) C++17
0 / 100
 5000 ms 13524 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define em emplace
#define eb emplace_back
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 1e18;
const int inf = 1e9;

int n, m, q;
ll l, c;
ll a[200010];
ll b[200010];
int nxt[200010];
int g[200010];
ll cost[200010];
bool chk[3010];
ll t[200010];
vector<pll> v;
ll dist[3010][3010];

int main() {
	fast;

	cin >> n >> m >> l >> c;

	for(int i=1; i<=n; i++) {
		cin >> a[i];
		t[i] = INF;
	}

	for(int i=1; i<=n; i++) {
		ll t = a[i] - c;

		t = t % l + l;

		nxt[i] = upper_bound(a+1, a+n+1, t % l) - a - 1;
		if(nxt[i] == 0) nxt[i] = n;
		
		cost[i] = (c - (a[i] - a[nxt[i]])) / l * l + (a[i] - a[nxt[i]]);
		while(cost[i] < c) cost[i] += l;
		while(cost[i] >= c+l) cost[i] -= l;
	}

	for(int i=1; i<=n; i++) {
		int j = 0, cnt = 0;
		for(j=i; nxt[j] != i && cnt <= n; j = nxt[j], cnt++) t[i] += cost[j];

		if(nxt[j] == i) t[i] += cost[j];
		else t[i] = INF;
	}

	for(int i=1; i<=m; i++) {
		cin >> b[i];

		int k = upper_bound(a+1, a+n+1, b[i]) - a - 1;
		if(k == 0) k = n;
		
		ll d = b[i] - a[k];
		if(d < 0) d += l;

		g[i] = k;

		for(int j = k; !dist[i][j]; j = nxt[j]) {
			dist[i][j] = d;

			d += cost[j];
		}
	}

	cin >> q;

	for(int i=1; i<=q; i++) {
		int v;
		ll T, ans = 0;
		cin >> v >> T;

		for(int j=1; j<=m; j++) {
			if(dist[j][v] <= T && dist[j][v] != 0) {
				ans += (T - dist[j][v]) / t[v] + 1;
			}
		}

		cout << ans << "\n";
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5085 ms 13524 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -