oj.uz

Submission #260943

# Submission time Handle Problem Language Result Execution time Memory
260943 2020-08-11T08:20:33 Z 임성재(#5066) Harvest (JOI20_harvest) C++17
0 / 100
 5000 ms 71416 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];

void dfs(int x) {
	if(chk[x]) {
		ll T = cost[x];
		for(int i=nxt[x]; i != x; i = nxt[i]) 
			T += cost[i];

		t[x] = T;

		for(int i=nxt[x]; i != x; i = nxt[i]) 
			t[i] = T;

		return;
	}
	chk[x] = true;
	dfs(nxt[x]);
}

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];
		}
	}

	for(int i=1; i<=n; i++) 
		if(!chk[i]) dfs(i);

	for(int i=1; i<=m; i++) {
		for(int j=1; j<=n; j++) {
			if(!dist[i][j]) dist[i][j] = INF;
		}
	}

	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) {
				ans += (T - dist[j][v]) / t[v] + 1;
			}
		}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 212 ms 71316 KB Output is correct
3 Correct 172 ms 71416 KB Output is correct
4 Execution timed out 5053 ms 71304 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 212 ms 71316 KB Output is correct
3 Correct 172 ms 71416 KB Output is correct
4 Execution timed out 5053 ms 71304 KB Time limit exceeded
5 Halted 0 ms 0 KB -