| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 715501 |
2023-03-27T04:44:53 Z |
pavement |
Harvest (JOI20_harvest) |
C++17 |
|
5000 ms |
37412 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
int N, M, L, C, Q, A[200005], B[200005], off[200005], lnk[200005], sz[200005], ans[200005];
bool on_cycle[200005];
ii to[200005];
vector<ii> adj[200005], qu[200005];
ordered_set<ii> S[200005];
int find(int x) {
if (x == lnk[x]) return x;
return lnk[x] = find(lnk[x]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (sz[b] > sz[a]) swap(a, b);
sz[a] += sz[b];
lnk[b] = a;
}
void solve_tree(int n) {
for (auto [u, w] : adj[n]) {
solve_tree(u);
off[u] += w;
if (S[u].size() > S[n].size()) {
swap(S[n], S[u]);
swap(off[n], off[u]);
}
for (auto v : S[u]) {
S[n].insert(mp(v.first + off[u] - off[n], v.second));
}
}
for (auto [t, idx] : qu[n]) {
ans[idx] = S[n].order_of_key(mp(t - off[n], (int)1e16));
}
}
main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> L >> C;
for (int i = 1; i <= N; i++) {
cin >> A[i];
lnk[i] = i;
sz[i] = 1;
}
for (int i = 1; i <= N; i++) {
int pos = ((A[i] - C) % L + L) % L;
auto it = upper_bound(A + 1, A + 1 + N, pos);
if (it == A + 1) {
to[i] = mp(N, pos + L - A[N] + C);
} else {
--it;
to[i] = mp(it - A, pos - *it + C);
}
unite(i, to[i].first);
adj[to[i].first].eb(i, to[i].second);
}
for (int i = 1; i <= M; i++) {
cin >> B[i];
auto it = lower_bound(A + 1, A + 1 + N, B[i]);
if (it == A + 1) {
S[N].insert(mp(B[i] + L - A[N], i));
} else {
--it;
S[it - A].insert(mp(B[i] - *it, i));
}
}
cin >> Q;
for (int i = 1, V, T; i <= Q; i++) {
cin >> V >> T;
qu[V].eb(T, i);
}
// handle nodes not on cycle
for (int i = 1; i <= N; i++) {
if (i == find(i)) {
int tort = i, hare = i;
do {
hare = to[to[hare].first].first;
tort = to[tort].first;
} while (tort != hare);
do {
on_cycle[tort] = 1;
tort = to[tort].first;
} while (tort != hare);
}
}
for (int i = 1; i <= N; i++) {
if (on_cycle[i]) {
for (auto [u, w] : adj[i]) if (!on_cycle[u]) {
solve_tree(u);
off[u] += w;
if (S[u].size() > S[i].size()) {
swap(S[i], S[u]);
swap(off[i], off[u]);
}
for (auto v : S[u]) {
S[i].insert(mp(v.first + off[u] - off[i], v.second));
}
}
}
}
// handle nodes on cycle
for (int i = 1; i <= N; i++) {
if (i == find(i)) {
int tort = i, hare = i;
do {
hare = to[to[hare].first].first;
tort = to[tort].first;
} while (tort != hare);
vector<int> ord;
int len = 0;
do {
ord.pb(tort);
len += to[tort].second;
tort = to[tort].first;
} while (tort != hare);
//~ int P = 0;
//~ for (auto x : ord) {
//~ cout << "AT " << x << '\n';
//~ for (auto [v, _] : S[x]) {
//~ v += off[x];
//~ cout << "ADD " << ((P - v) % len + len) % len << '\n';
//~ }
//~ for (auto [t, idx] : qu[x]) {
//~ int b = t - P + 1;
//~ cout << "QUERY " << 0 << ' ' << (len - (b % len)) % len << '\n';
//~ cout << "QUERY " << (len - (b % len)) % len + 1 << ' ' << len - 1 << '\n';
//~ }
//~ P += to[x].second;
//~ }
for (auto x : ord) {
for (auto [t, idx] : qu[x]) {
int cur = x, P = 0;
do {
P += to[cur].second;
cur = to[cur].first;
// dist cur -> x = len - P
for (auto [v, _] : S[cur]) {
if (t - v - (len - P) + 1 >= 0) {
ans[idx] += (t - v - (len - P) + len) / len;
}
}
} while (cur != x);
}
}
}
}
for (int i = 1; i <= Q; i++) {
cout << ans[i] << '\n';
}
}
Compilation message
harvest.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
65 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
28784 KB |
Output is correct |
| 2 |
Correct |
24 ms |
29168 KB |
Output is correct |
| 3 |
Correct |
113 ms |
29428 KB |
Output is correct |
| 4 |
Incorrect |
35 ms |
29676 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5023 ms |
37412 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
28784 KB |
Output is correct |
| 2 |
Correct |
24 ms |
29168 KB |
Output is correct |
| 3 |
Correct |
113 ms |
29428 KB |
Output is correct |
| 4 |
Incorrect |
35 ms |
29676 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
