Submission #780508

#	Time	Username	Problem	Language	Result	Execution time	Memory
780508		ymm	Harvest (JOI20_harvest)	C++17	5 / 100	5051 ms	90732 KiB

harvest

#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 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 75