oj.uz

Submission #513333

# Submission time Handle Problem Language Result Execution time Memory
513333 2022-01-17T05:28:27 Z 8e7 Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 92564 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b) {cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int a[maxn], b[maxn], to[maxn];
ll dis[maxn], cy[maxn];
bool vis[maxn];
vector<ll> ch[maxn];
pii s[maxn];
int main() {
	io
	int n, m, l, c;
	cin >> n >> m >> l >> c;
	for (int i = 0;i < n;i++) cin >> a[i], s[i] = {a[i], i};
	for (int i = 0;i < m;i++) cin >> b[i];
	sort(s, s + n);
	for (int i = 0;i < n;i++) {
		int pos =((s[i].ff - c)%l + l)%l;
		int ind = upper_bound(s, s + n, make_pair(pos, maxn)) - s - 1;
		if (ind < 0) ind = n - 1;
		to[s[i].ss] = s[ind].ss;
		dis[s[i].ss] = c + (pos - s[ind].ff + l)%l;
	}
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) vis[j] = 0;
		int cur = i;
		ll d = 0;
		do {
			vis[cur] = 1;
			d += dis[cur];
			cur = to[cur];
		} while (!vis[cur]);
		if (cur == i) {
			cy[i] = d;
		}
	}
	for (int i = 0;i < m;i++) {
		for (int j = 0;j < n;j++) vis[j] = 0;
		int cur = upper_bound(s, s + n, make_pair(b[i], maxn)) - s - 1;
		if (cur < 0) cur = n - 1;	
		ll d = (b[i] - s[cur].ff + l)%l;
		do {
			ch[cur].push_back(d);
			vis[cur] = 1;
			d += dis[cur];
			cur = to[cur];
		} while (!vis[cur]);
	}
	int q;
	cin >> q;
	for (int i = 0;i < q;i++) {
		ll l, t;
		cin >> l >> t;	
		l--;
		ll ans = 0;
		for (auto x:ch[l]) {
			if (x > t) continue;
			if (cy[l]) {
				ans += (t - x) / cy[l] + 1;	
			} else {
				ans++;
			}
		}
		cout << ans << "\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 4 ms 2892 KB Output is correct
3 Correct 90 ms 2968 KB Output is correct
4 Correct 13 ms 6916 KB Output is correct
5 Correct 88 ms 50480 KB Output is correct
6 Correct 94 ms 50240 KB Output is correct
7 Correct 89 ms 51008 KB Output is correct
8 Correct 4 ms 2892 KB Output is correct
9 Correct 4 ms 2892 KB Output is correct
10 Correct 3 ms 3020 KB Output is correct
11 Correct 4 ms 2956 KB Output is correct
12 Correct 178 ms 92564 KB Output is correct
13 Correct 275 ms 92528 KB Output is correct
14 Correct 117 ms 50884 KB Output is correct
15 Correct 47 ms 29036 KB Output is correct
16 Correct 47 ms 28820 KB Output is correct
17 Correct 47 ms 28944 KB Output is correct
18 Correct 49 ms 27388 KB Output is correct
19 Correct 42 ms 27732 KB Output is correct
20 Correct 42 ms 26680 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 4 ms 2892 KB Output is correct
3 Correct 90 ms 2968 KB Output is correct
4 Correct 13 ms 6916 KB Output is correct
5 Correct 88 ms 50480 KB Output is correct
6 Correct 94 ms 50240 KB Output is correct
7 Correct 89 ms 51008 KB Output is correct
8 Correct 4 ms 2892 KB Output is correct
9 Correct 4 ms 2892 KB Output is correct
10 Correct 3 ms 3020 KB Output is correct
11 Correct 4 ms 2956 KB Output is correct
12 Correct 178 ms 92564 KB Output is correct
13 Correct 275 ms 92528 KB Output is correct
14 Correct 117 ms 50884 KB Output is correct
15 Correct 47 ms 29036 KB Output is correct
16 Correct 47 ms 28820 KB Output is correct
17 Correct 47 ms 28944 KB Output is correct
18 Correct 49 ms 27388 KB Output is correct
19 Correct 42 ms 27732 KB Output is correct
20 Correct 42 ms 26680 KB Output is correct
21 Execution timed out 5078 ms 8524 KB Time limit exceeded
22 Halted 0 ms 0 KB -