oj.uz

Submission #780508

# Submission time Handle Problem Language Result Execution time Memory
780508 2023-07-12T09:41:30 Z ymm Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 90732 KB 
#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
#define LoopR(x, l, r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 1024*3;

int nxt[N];
ll delta[N];
int first[N];
ll fdelta[N];

ll T[N][N];
bool inc[N][N], outc[N][N];
ll precs[N], cs[N];

int a[N], b[N];
int n, m;
ll l, c;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m >> l >> c;
	Loop (i,0,n)
		cin >> a[i];
	Loop (i,0,m)
		cin >> b[i];
	Loop (i,0,m) {
		fdelta[i] = l;
		Loop (j,0,n) {
			ll x = b[i] - a[j];
			x = x < 0? x + l: x;
			if (fdelta[i] > x) {
				fdelta[i] = x;
				first[i] = j;
			}
		}
	}
	Loop (j,0,n) {
		ll x = (a[j] - c);
		x = (x%l+l)%l;
		//cout << x << "--\n";
		int p = upper_bound(a, a+n, x) - a - 1;
		if (p == -1) {
			nxt[j] = n-1;
			delta[j] = c + x - a[n-1] + l;
		} else {
			nxt[j] = p;
			delta[j] = c + x - a[p];
		}
		//cout << i << ' ' << j << " nxt is " << nxt[i][j] << '\n';
	}
	Loop (i,0,m) {
		int p = first[i];
		T[i][p] = fdelta[i];
		outc[i][p] = 1;
		for (;;) {
			int p2 = nxt[p];
			if (outc[i][p2]) {
				cs[i] = T[i][p] + delta[p];
				precs[i] = T[i][p2];
				cs[i] -= precs[i];
				p = p2;
				break;
			}
			T[i][p2] = T[i][p] + delta[p];
			outc[i][p2] = 1;
			p = p2;
		}
		for (int v = nxt[p]; v != p; v = nxt[v]) {
			T[i][v] -= T[i][p];
			outc[i][v] = 0;
			inc[i][v] = 1;
		}
		T[i][p] = 0;
		outc[i][p] = 0;
		inc[i][p] = 1;
	}
	int q;
	cin >> q;
	while (q--) {
		int v;
		ll t;
		cin >> v >> t;
		--v;
		ll ans = 0;
		Loop (i,0,m) {
			if (outc[i][v]) {
				ans += T[i][v] <= t;
				continue;
			}
			if (!inc[i][v] || t < precs[i])
				continue;
			ll cnt = (t - precs[i]) / cs[i];
			ans += cnt;
			ans += T[i][v] <= t - precs[i] - cnt*cs[i];
		}
		cout << ans << '\n';
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 125 ms 30720 KB Output is correct
3 Correct 189 ms 30764 KB Output is correct
4 Correct 186 ms 90732 KB Output is correct
5 Correct 164 ms 67556 KB Output is correct
6 Correct 174 ms 67748 KB Output is correct
7 Correct 163 ms 67908 KB Output is correct
8 Correct 137 ms 40664 KB Output is correct
9 Correct 128 ms 40676 KB Output is correct
10 Correct 142 ms 41180 KB Output is correct
11 Correct 130 ms 40844 KB Output is correct
12 Correct 279 ms 90732 KB Output is correct
13 Correct 313 ms 90724 KB Output is correct
14 Correct 253 ms 90680 KB Output is correct
15 Correct 198 ms 71444 KB Output is correct
16 Correct 157 ms 68612 KB Output is correct
17 Correct 157 ms 67004 KB Output is correct
18 Correct 138 ms 49096 KB Output is correct
19 Correct 148 ms 53636 KB Output is correct
20 Correct 142 ms 51288 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 125 ms 30720 KB Output is correct
3 Correct 189 ms 30764 KB Output is correct
4 Correct 186 ms 90732 KB Output is correct
5 Correct 164 ms 67556 KB Output is correct
6 Correct 174 ms 67748 KB Output is correct
7 Correct 163 ms 67908 KB Output is correct
8 Correct 137 ms 40664 KB Output is correct
9 Correct 128 ms 40676 KB Output is correct
10 Correct 142 ms 41180 KB Output is correct
11 Correct 130 ms 40844 KB Output is correct
12 Correct 279 ms 90732 KB Output is correct
13 Correct 313 ms 90724 KB Output is correct
14 Correct 253 ms 90680 KB Output is correct
15 Correct 198 ms 71444 KB Output is correct
16 Correct 157 ms 68612 KB Output is correct
17 Correct 157 ms 67004 KB Output is correct
18 Correct 138 ms 49096 KB Output is correct
19 Correct 148 ms 53636 KB Output is correct
20 Correct 142 ms 51288 KB Output is correct
21 Execution timed out 5051 ms 33896 KB Time limit exceeded
22 Halted 0 ms 0 KB -