| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 715896 |
2023-03-28T11:11:25 Z |
pavement |
Harvest (JOI20_harvest) |
C++17 |
|
1907 ms |
161520 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, root, A[200005], B[200005], off[200005], lnk[200005], sz[200005], ans[200005];
bool on_cycle[200005];
ii to[200005];
vector<int> S[200005];
vector<ii> adj[200005], qu[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;
}
template <class T>
struct wavelet_matrix {
using size_type = uint32_t;
struct bit_vector {
static constexpr size_type wsize = 64;
static size_type rank64(uint64_t x, size_type i) {
return __builtin_popcountll(x & ((1ULL << i) - 1));
}
#pragma pack(4)
struct block_t {
uint64_t bit;
size_type sum;
};
#pragma pack()
size_type n, zeros;
vector<block_t> block;
bit_vector(size_type _n = 0) : n(_n), block(n / wsize + 1) {}
int operator[](size_type i) const {
return block[i / wsize].bit >> i % wsize & 1;
}
void set(size_type i) {
block[i / wsize].bit |= (uint64_t)1 << i % wsize;
}
void build() {
for (size_type j = 0; j < n / wsize; ++j)
block[j + 1].sum =
block[j].sum + __builtin_popcountll(block[j].bit);
zeros = rank0(n);
}
size_type rank0(size_type i) const { return i - rank1(i); }
size_type rank1(size_type i) const {
auto&& e = block[i / wsize];
return e.sum + rank64(e.bit, i % wsize);
}
};
size_type n, lg;
vector<T> a;
vector<bit_vector> bv;
wavelet_matrix(size_type _n = 0) : n(_n), a(n) {}
wavelet_matrix(const vector<T>& _a) : n(_a.size()), a(_a) { build(); }
T& operator[](size_type i) { return a[i]; }
void build() {
lg = __lg(max<T>(
*max_element(begin(a), end(a)), 1)) +
1;
bv.assign(lg, n);
vector<T> cur = a, nxt(n);
for (auto h = lg; h--;) {
for (size_type i = 0; i < n; ++i)
if (cur[i] >> h & 1) bv[h].set(i);
bv[h].build();
array it{begin(nxt), begin(nxt) + bv[h].zeros};
for (size_type i = 0; i < n; ++i) *it[bv[h][i]]++ = cur[i];
swap(cur, nxt);
}
}
// find kth element in [l, r), 0 indexed
T kth(size_type l, size_type r, size_type k) const {
T res = 0;
for (auto h = lg; h--;) {
auto l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
if (k < r0 - l0)
l = l0, r = r0;
else {
k -= r0 - l0;
res |= (T)1 << h;
l += bv[h].zeros - l0;
r += bv[h].zeros - r0;
}
}
return res;
}
// count i in [l..r) satisfying a[i] < ub
size_type count(size_type l, size_type r, T ub) const {
if (ub >= (T)1 << lg) return r - l;
size_type res = 0;
for (auto h = lg; h--;) {
auto l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
if (~ub >> h & 1)
l = l0, r = r0;
else {
res += r0 - l0;
l += bv[h].zeros - l0;
r += bv[h].zeros - r0;
}
}
return res;
}
size_type count(size_type l, size_type r, T lb, T ub) const {
return count(l, r, ub) - count(l, r, lb);
}
};
template <class T>
auto zip(const vector<T>& a) {
int n = size(a);
vector<pair<T, int>> p(n);
for (int i = 0; i < n; ++i) p[i] = {a[i], i};
sort(begin(p), end(p));
vector<int> na(n);
vector<T> v;
for (int k = 0, rnk = -1; k < n; ++k) {
if (k == 0 or p[k - 1].first < p[k].first)
v.push_back(p[k].first), ++rnk;
na[p[k].second] = rnk;
}
return make_pair(na, v);
}
vector<int> wav;
vector<iiii> to_qry;
void solve_tree(int n, int d) {
assert(!on_cycle[n]);
int lb = (int)wav.size();
for (auto v : S[n]) {
wav.pb(v - d);
S[root].pb(v + d);
}
for (auto [u, w] : adj[n]) {
solve_tree(u, d + w);
}
for (auto [v, idx] : qu[n]) {
to_qry.eb(lb, (int)wav.size(), v - d + 1, idx);
}
}
vector<iii> adds[400005], qus[400005];
stack<int> updated;
int ft[400005];
int ls(int x) { return x & -x; }
int ft_qry(int p) {
int r = 0;
for (; p; p -= ls(p)) r += ft[p];
return r;
}
void ft_upd(int p, int sz) {
for (; p <= sz; p += ls(p)) {
updated.push(p);
ft[p]++;
}
}
void ft_reset() {
while (!updated.empty()) {
int cur = updated.top();
ft[cur] = 0;
updated.pop();
}
}
void cdq(int l, int r) {
if (l == r) return;
int m = (l + r) / 2;
vector<iii> sort_by;
for (int i = l; i <= m; i++) {
for (auto [a, q, r] : adds[i]) {
sort_by.eb(a, q, r);
}
}
for (int i = m + 1; i <= r; i++) {
for (auto [b, r, idx] : qus[i]) {
sort_by.eb(b, r, -idx);
}
}
int pf = 0;
ordered_set<ii> O;
sort(sort_by.begin(), sort_by.end(), [](const auto &lhs, const auto &rhs) {
if (g0(lhs) == g0(rhs) && (g2(lhs) >= 0) != (g2(rhs) >= 0)) return g2(lhs) > g2(rhs);
else return lhs < rhs;
});
vector<int> disc;
for (auto [a, b, c] : sort_by) {
if (c < 0) disc.pb(b);
else disc.pb(c);
}
sort(disc.begin(), disc.end());
disc.erase(unique(disc.begin(), disc.end()), disc.end());
ft_reset();
for (auto [a, b, c] : sort_by) {
if (c < 0) {
b = lower_bound(disc.begin(), disc.end(), b) - disc.begin() + 1;
ans[-c] -= ft_qry(b) + pf;
} else {
pf += b;
c = lower_bound(disc.begin(), disc.end(), c) - disc.begin() + 1;
ft_upd(c, (int)disc.size());
}
}
cdq(l, m);
cdq(m + 1, r);
}
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].pb(B[i] + L - A[N]);
} else {
--it;
S[it - A].pb(B[i] - *it);
}
}
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]) {
root = i;
wav.clear();
to_qry.clear();
for (auto [u, w] : adj[i]) if (!on_cycle[u]) {
solve_tree(u, w);
}
if (!wav.empty()) {
auto [na, v] = zip(wav);
wavelet_matrix wm(na);
for (auto [l, r, k, idx] : to_qry) {
ans[idx] += wm.count(l, r, k);
}
}
}
}
// 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, cnt = 0;
vector<int> disc;
ft_reset();
qus[0].clear();
for (auto x : ord) {
adds[cnt].clear();
for (auto v : S[x]) {
int a = v + off[x] - P;
int q2 = a / len, r2 = a % len;
if (r2 < 0) {
r2 += len;
q2--;
}
adds[cnt].eb(a, q2, len - r2);
disc.pb(a);
}
qus[cnt + 1].clear();
for (auto [t, idx] : qu[x]) {
int b = t - P + len;
int q1 = b / len, r1 = b % len;
if (r1 < 0) {
r1 += len;
q1--;
}
qus[cnt + 1].eb(b, len - r1 - 1, idx);
disc.pb(b);
}
P += to[x].second;
cnt++;
}
P = 0;
sort(disc.begin(), disc.end());
disc.erase(unique(disc.begin(), disc.end()), disc.end());
for (auto x : ord) {
for (auto v : S[x]) {
int a = v + off[x] - P;
int da = lower_bound(disc.begin(), disc.end(), a) - disc.begin() + 1;
ft_upd(da, (int)disc.size());
}
for (auto [t, idx] : qu[x]) {
int b = t - P + len;
int q1 = b / len, r1 = b % len;
if (r1 < 0) {
r1 += len;
q1--;
}
int db = lower_bound(disc.begin(), disc.end(), b) - disc.begin() + 1;
ans[idx] += q1 * ft_qry(db);
}
P += to[x].second;
}
adds[cnt].clear();
cnt++;
if (cnt) cdq(0, cnt - 1);
reverse(ord.begin(), ord.end());
P = cnt = 0;
disc.clear();
ft_reset();
for (auto x : ord) {
adds[cnt].clear();
qus[cnt].clear();
P += to[x].second;
for (auto v : S[x]) {
int a = v + off[x] + P;
int q2 = a / len, r2 = a % len;
if (r2 < 0) {
r2 += len;
q2--;
}
disc.pb(a);
adds[cnt].eb(a, q2, len - r2);
}
for (auto [t, idx] : qu[x]) {
int b = t + P;
int q1 = b / len, r1 = b % len;
if (r1 < 0) {
r1 += len;
q1--;
}
qus[cnt].eb(b, len - r1 - 1, idx);
disc.pb(b);
}
cnt++;
}
P = 0;
sort(disc.begin(), disc.end());
disc.erase(unique(disc.begin(), disc.end()), disc.end());
for (auto x : ord) {
P += to[x].second;
for (auto [t, idx] : qu[x]) {
int b = t + P;
int q1 = b / len, r1 = b % len;
if (r1 < 0) {
r1 += len;
q1--;
}
int db = lower_bound(disc.begin(), disc.end(), b) - disc.begin() + 1;
ans[idx] += q1 * ft_qry(db);
}
for (auto v : S[x]) {
int a = v + off[x] + P;
int da = lower_bound(disc.begin(), disc.end(), a) - disc.begin() + 1;
ft_upd(da, (int)disc.size());
}
}
if (cnt) cdq(0, cnt - 1);
}
}
for (int i = 1; i <= Q; i++) {
cout << ans[i] << '\n';
}
}
Compilation message
harvest.cpp:245:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
245 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
33744 KB |
Output is correct |
| 2 |
Correct |
21 ms |
33876 KB |
Output is correct |
| 3 |
Correct |
23 ms |
34388 KB |
Output is correct |
| 4 |
Incorrect |
28 ms |
34504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
255 ms |
60720 KB |
Output is correct |
| 2 |
Correct |
203 ms |
58516 KB |
Output is correct |
| 3 |
Correct |
211 ms |
55176 KB |
Output is correct |
| 4 |
Correct |
339 ms |
74580 KB |
Output is correct |
| 5 |
Correct |
181 ms |
87336 KB |
Output is correct |
| 6 |
Correct |
194 ms |
93980 KB |
Output is correct |
| 7 |
Correct |
171 ms |
65316 KB |
Output is correct |
| 8 |
Correct |
161 ms |
65248 KB |
Output is correct |
| 9 |
Correct |
1012 ms |
82952 KB |
Output is correct |
| 10 |
Correct |
1907 ms |
161520 KB |
Output is correct |
| 11 |
Correct |
1095 ms |
83192 KB |
Output is correct |
| 12 |
Correct |
1084 ms |
83160 KB |
Output is correct |
| 13 |
Correct |
1125 ms |
83260 KB |
Output is correct |
| 14 |
Correct |
1395 ms |
135608 KB |
Output is correct |
| 15 |
Correct |
917 ms |
74500 KB |
Output is correct |
| 16 |
Correct |
184 ms |
81388 KB |
Output is correct |
| 17 |
Correct |
192 ms |
81112 KB |
Output is correct |
| 18 |
Correct |
137 ms |
59216 KB |
Output is correct |
| 19 |
Correct |
133 ms |
59100 KB |
Output is correct |
| 20 |
Correct |
208 ms |
65400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
33744 KB |
Output is correct |
| 2 |
Correct |
21 ms |
33876 KB |
Output is correct |
| 3 |
Correct |
23 ms |
34388 KB |
Output is correct |
| 4 |
Incorrect |
28 ms |
34504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
