## Submission #216901

# Submission time Handle Problem Language Result Execution time Memory
216901 2020-03-28T10:56:41 Z rama_pang Harvest (JOI20_harvest) C++14
100 / 100
766 ms 95780 KB
```#include <bits/stdc++.h>
using namespace std;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

long long floor_div(long long a, long long b) { // integer floor division
return (a / b) - ((a ^ b) < 0 && a % b);
}

namespace Treap {

struct TreapNode {
int prior, sz;
long long value, lazy = 0;
TreapNode *l, *r;
TreapNode(long long v = 0) : prior(rnd()), sz(1), value(v), l(NULL), r(NULL) {}
};

using pt = TreapNode*;

int sz(pt t) { return t ? t->sz : 0; }
void upd(pt t) { if (t) t->sz = sz(t->l) + sz(t->r) + 1; }
void apply(pt t, long long x) { if (t) t->value += x, t->lazy += x; }

void push(pt t) {
if (!t) return;
apply(t->l, t->lazy);
apply(t->r, t->lazy);
t->lazy = 0;
}

void split(pt t, pt &l, pt &r, long long key) { // l will have all values <= key
push(t);
if (!t) {
l = r = NULL;
} else if (t->value > key) {
split(t->l, l, t->l, key), r = t;
} else {
split(t->r, t->r, r, key), l = t;
}
upd(t);
}

void merge(pt &t, pt l, pt r) {
push(l), push(r);
if (!l || !r) {
t = l ? l : r;
} else if (l->prior > r->prior) {
merge(l->r, l->r, r), t = l;
} else {
merge(r->l, l, r->l), t = r;
}
upd(t);
}

void erase(pt t, long long x) {
push(t);
if (!t) return;
if (t->value > x) {
erase(t->l, x);
} else if (t->value < x) {
erase(t->r, x);
} else if (t->value == x) {
pt to_be_del = t;
merge(t, t->l, t->r);
delete to_be_del;
}
upd(t);
}

void clear(pt t) {
if (!t) return;
clear(t->l);
clear(t->r);
t = NULL;
delete t;
}

void get(pt t, vector<long long> &res) {
push(t);
if (!t) return;
get(t->l, res);
res.emplace_back(t->value);
get(t->r, res);
}

void update(pt &root, long long x) { // increase all elements in treap by x under modulo mod
pt l, r;
apply(root, x);
}

void insert(pt &root, long long x) {
pt l, r;
split(root, l, r, x);
merge(l, l, new TreapNode(x));
merge(root, l, r);
}

vector<long long> get(pt root) {
vector<long long> res;
get(root, res);
return res;
}

int order_of_key(pt &root, long long x) { // find number of values <= x
pt l, r;
int res;
split(root, l, r, x);
res = sz(l);
merge(root, l, r);
return res;
}

pt unite(pt l, pt r) {
push(l), push(r);
if (!l) return r;
if (!r) return l;
if (l->prior < r->prior) swap(l, r);
pt lt, rt;
split(r, lt, rt, l->value);
l->l = unite(l->l, lt);
l->r = unite(l->r, rt);
upd(l);
return l;
}

}

int N, M, L, C;
vector<int> A, B;

vector<int> next_vertex; // next vertex A[] after a tree has just finished visited A[i] and gave it an apple
vector<int> next_distance; // distance to next_vertex (time needed)

vector<int> first_vertex; // first vertex that tree[] meets
vector<int> first_distance; // the distance in time

vector<bool> in_cycle; // whether a vertex v is part of a cycle or not
vector<long long> cycle_length; // the length of a cycle vertex v is part of

vector<int> cycle_start; // the start of the cycle, where pos[start] = 0
vector<long long> pos_in_cycle; // the positions / distance

namespace Naive { // O(N^2 log N) solution, unoptimized version of the main ideas for full solution

vector<multiset<long long>> meeting_time; // first time a vertex meets certain trees under modulo len
vector<long long> initial_overflow; // sum of all floor(i / len) for meeting_time (the original value)

void NaiveGetMeetingTime() { // Naive O(N^2 log N)
meeting_time.resize(N);
for (int ci = 0; ci < M; ci++) {
int v = first_vertex[ci];
long long len = first_distance[ci];
vector<bool> vis(N, false);

do {
vis[v] = true;
meeting_time[v].emplace(len);
len += next_distance[v];
v = next_vertex[v];
} while (!vis[v]);
}
}

long long NaiveQuery(int V, long long T) {
if (!in_cycle[V]) {
int lb = 0; // lower bound, will be implemented later
for (auto &i : meeting_time[V]) {
if (i <= T) lb++;
}
return lb;
}

// V is in a cycle
long long len = cycle_length[V];
long long res = 0;

for (auto &i : meeting_time[V]) {
long long cur = floor_div(T, len) - floor_div(i, len) + ((i % len) <= (T % len)); // equivalent to div(T - i, len) + 1
res += max(cur, 0ll);
}
return res;
}

}

void BuildGraph() {
{ // build initial graph
next_vertex.resize(N);
next_distance.resize(N);

for (int i = 0; i < N; i++) {
int next_loc = (A[i] - C) % L; // go counter clockwise
if (next_loc < 0) next_loc += L;
if (next_loc < A[0]) next_loc += L;
next_vertex[i] = upper_bound(begin(A), end(A), next_loc) - begin(A) - 1;
next_distance[i] = C + (next_loc - A[next_vertex[i]]);
}

first_vertex.resize(M);
first_distance.resize(M);

for (int i = 0; i < M; i++) {
int next_loc = B[i]; // go counter clockwise
if (next_loc < A[0]) next_loc += L;
first_vertex[i] = upper_bound(begin(A), end(A), next_loc) - begin(A) - 1;
first_distance[i] = (next_loc - A[first_vertex[i]]);
}
}

{ // find information about the cycles
int mark = 0;
vector<int> vis(N, 0);

in_cycle.resize(N, false);
cycle_length.resize(N, -1);

cycle_start.resize(N, -1);
pos_in_cycle.resize(N, -1);

auto Calc = [&](int i) {
mark++;
int cur = i;

do {
vis[cur] = mark;
cur = next_vertex[cur];
} while (!vis[cur]);

if (vis[cur] != mark) { // this cycle is already processed before
return;
}

int st = cur;
long long len = 0;

do {
cycle_start[cur] = st;
pos_in_cycle[cur] = len;

in_cycle[cur] = true;
len += next_distance[cur];
cur = next_vertex[cur];
} while (cur != st);

cycle_length[cur] = len;
};

// process cycles
for (int i = 0; i < N; i++) {
if (vis[i]) continue;
Calc(i);
}
}
}

vector<vector<pair<long long, int>>> query; // query[V] = (T, query_index)

vector<vector<long long>> first_meeting_cycle; // first time trees meet a cycle (time)
vector<vector<long long>> first_meeting_tree; // first time trees meet a non-cucle (which musy be a tree) (time)

void SolveTree() { // also solves the case for broken cycle
for (int i = 0; i < N; i++) {
if (in_cycle[i] && cycle_start[i] == next_vertex[i]) continue; // the edge to be cut in a broken cycle
if (!in_cycle[i] && in_cycle[next_vertex[i]]) continue;
}

vector<Treap::pt> treap(N, NULL);

function<void(int)> dfs = [&](int cur) {
for (auto &nxt : adj[cur]) {
dfs(nxt);
treap[cur] = unite(treap[cur], treap[nxt]);
}
for (auto &nw : first_meeting_tree[cur]) {
Treap::insert(treap[cur], nw);
}
for (auto &q : query[cur]) {
}
Treap::update(treap[cur], next_distance[cur]);
};

// calculate answer for tree part
for (int i = 0; i < N; i++) {
if (!in_cycle[i] && in_cycle[next_vertex[i]]) {
dfs(i);
// next_vertex is now part of a cycle
vector<long long> elements = Treap::get(treap[i]);
Treap::clear(treap[i]);
for (auto &e : elements) {
first_meeting_cycle[next_vertex[i]].emplace_back(e);
first_meeting_tree[next_vertex[i]].emplace_back(e);
}
}
}

// calculate contribution of broken cycle
for (int i = 0; i < N; i++) {
if (in_cycle[i] && cycle_start[i] == next_vertex[i]) {
dfs(i);
Treap::clear(treap[i]);
}
}
}

void SolveCycle(int r) { // solves the case for cycles, excluding the broken cycle case
long long initial_overflow = 0;
long long len = cycle_length[r];

int cur = r;
Treap::pt treap = NULL;

vector<long long> all_meeting_time;
vector<pair<long long, int>> all_queries; // pair of (T - pos[orginal_position], query_id)

do {
for (auto &nw : first_meeting_cycle[cur]) {
long long distance = nw + (len - pos_in_cycle[cur]);
all_meeting_time.emplace_back(distance);
}
for (auto &q : query[cur]) {
all_queries.emplace_back(q.first - pos_in_cycle[cur], q.second);
}
cur = next_vertex[cur];
} while (cur != r);

sort(begin(all_meeting_time), end(all_meeting_time), greater<long long>());
sort(begin(all_queries), end(all_queries));

for (auto &q : all_queries) {
while (!all_meeting_time.empty() && all_meeting_time.back() <= q.first) {
Treap::insert(treap, all_meeting_time.back() % len);
initial_overflow += floor_div(all_meeting_time.back(), len);
all_meeting_time.pop_back();
}
answer[q.second] += 1ll * floor_div(q.first, len) * Treap::sz(treap) - initial_overflow + Treap::order_of_key(treap, q.first % len);
}

Treap::clear(treap);
}

void SolveCycle() {
for (int i = 0; i < N; i++) {
if (in_cycle[i] && cycle_start[i] == i) {
SolveCycle(i);
}
}
}

void SolveQuery() {
first_meeting_cycle.resize(N);
first_meeting_tree.resize(N);

for (int i = 0; i < M; i++) {
int v = first_vertex[i];
if (in_cycle[v]) {
first_meeting_cycle[v].emplace_back(first_distance[i]);
first_meeting_tree[v].emplace_back(first_distance[i]);
} else {
first_meeting_tree[v].emplace_back(first_distance[i]);
}
}

SolveTree();
SolveCycle();
}

void Solve() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);

cin >> N >> M >> L >> C;

A.resize(N), B.resize(M);
for (auto &i : A) cin >> i;
for (auto &i : B) cin >> i;

int Q;
cin >> Q;

query.resize(N);

for (int i = 0; i < Q; i++) {
int V; long long T;
cin >> V >> T;
query[--V].emplace_back(T, i);
}

BuildGraph();
SolveQuery();

for (int i = 0; i < Q; i++) {
}
}

int main() {
Solve();
return 0;
}
```

### Compilation message

```harvest.cpp: In function 'void Treap::update(Treap::TreapNode*&, long long int)':
harvest.cpp:88:8: warning: unused variable 'l' [-Wunused-variable]
pt l, r;
^
harvest.cpp:88:11: warning: unused variable 'r' [-Wunused-variable]
pt l, r;
^```

#### Subtask #1 5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 9 ms 1280 KB Output is correct
3 Correct 10 ms 1280 KB Output is correct
4 Correct 10 ms 1408 KB Output is correct
5 Correct 10 ms 1792 KB Output is correct
6 Correct 11 ms 1792 KB Output is correct
7 Correct 11 ms 1792 KB Output is correct
8 Correct 10 ms 1408 KB Output is correct
9 Correct 9 ms 1408 KB Output is correct
10 Correct 10 ms 1408 KB Output is correct
11 Correct 9 ms 1408 KB Output is correct
12 Correct 10 ms 1536 KB Output is correct
13 Correct 13 ms 1664 KB Output is correct
14 Correct 14 ms 1536 KB Output is correct
15 Correct 10 ms 1664 KB Output is correct
16 Correct 12 ms 1664 KB Output is correct
17 Correct 11 ms 1664 KB Output is correct
18 Correct 10 ms 1536 KB Output is correct
19 Correct 10 ms 1536 KB Output is correct
20 Correct 10 ms 1536 KB Output is correct

#### Subtask #2 20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 15588 KB Output is correct
2 Correct 228 ms 45160 KB Output is correct
3 Correct 228 ms 41192 KB Output is correct
4 Correct 322 ms 42764 KB Output is correct
5 Correct 246 ms 66280 KB Output is correct
6 Correct 254 ms 66284 KB Output is correct
7 Correct 188 ms 41320 KB Output is correct
8 Correct 200 ms 42888 KB Output is correct
9 Correct 398 ms 66140 KB Output is correct
10 Correct 261 ms 65144 KB Output is correct
11 Correct 473 ms 66152 KB Output is correct
12 Correct 466 ms 66152 KB Output is correct
13 Correct 496 ms 66280 KB Output is correct
14 Correct 311 ms 63876 KB Output is correct
15 Correct 369 ms 56808 KB Output is correct
16 Correct 251 ms 56936 KB Output is correct
17 Correct 225 ms 56808 KB Output is correct
18 Correct 142 ms 22452 KB Output is correct
19 Correct 160 ms 22324 KB Output is correct
20 Correct 201 ms 45288 KB Output is correct

#### Subtask #3 75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 9 ms 1280 KB Output is correct
3 Correct 10 ms 1280 KB Output is correct
4 Correct 10 ms 1408 KB Output is correct
5 Correct 10 ms 1792 KB Output is correct
6 Correct 11 ms 1792 KB Output is correct
7 Correct 11 ms 1792 KB Output is correct
8 Correct 10 ms 1408 KB Output is correct
9 Correct 9 ms 1408 KB Output is correct
10 Correct 10 ms 1408 KB Output is correct
11 Correct 9 ms 1408 KB Output is correct
12 Correct 10 ms 1536 KB Output is correct
13 Correct 13 ms 1664 KB Output is correct
14 Correct 14 ms 1536 KB Output is correct
15 Correct 10 ms 1664 KB Output is correct
16 Correct 12 ms 1664 KB Output is correct
17 Correct 11 ms 1664 KB Output is correct
18 Correct 10 ms 1536 KB Output is correct
19 Correct 10 ms 1536 KB Output is correct
20 Correct 10 ms 1536 KB Output is correct
21 Correct 239 ms 15588 KB Output is correct
22 Correct 228 ms 45160 KB Output is correct
23 Correct 228 ms 41192 KB Output is correct
24 Correct 322 ms 42764 KB Output is correct
25 Correct 246 ms 66280 KB Output is correct
26 Correct 254 ms 66284 KB Output is correct
27 Correct 188 ms 41320 KB Output is correct
28 Correct 200 ms 42888 KB Output is correct
29 Correct 398 ms 66140 KB Output is correct
30 Correct 261 ms 65144 KB Output is correct
31 Correct 473 ms 66152 KB Output is correct
32 Correct 466 ms 66152 KB Output is correct
33 Correct 496 ms 66280 KB Output is correct
34 Correct 311 ms 63876 KB Output is correct
35 Correct 369 ms 56808 KB Output is correct
36 Correct 251 ms 56936 KB Output is correct
37 Correct 225 ms 56808 KB Output is correct
38 Correct 142 ms 22452 KB Output is correct
39 Correct 160 ms 22324 KB Output is correct
40 Correct 201 ms 45288 KB Output is correct
41 Correct 559 ms 72728 KB Output is correct
42 Correct 297 ms 58984 KB Output is correct
43 Correct 182 ms 39568 KB Output is correct
44 Correct 570 ms 58128 KB Output is correct
45 Correct 490 ms 94364 KB Output is correct
46 Correct 520 ms 95048 KB Output is correct
47 Correct 575 ms 95780 KB Output is correct
48 Correct 546 ms 93892 KB Output is correct
49 Correct 540 ms 94148 KB Output is correct
50 Correct 356 ms 69600 KB Output is correct
51 Correct 487 ms 74428 KB Output is correct
52 Correct 614 ms 89184 KB Output is correct
53 Correct 766 ms 89968 KB Output is correct
54 Correct 613 ms 89072 KB Output is correct
55 Correct 565 ms 86304 KB Output is correct
56 Correct 582 ms 85060 KB Output is correct
57 Correct 526 ms 85832 KB Output is correct
58 Correct 693 ms 86736 KB Output is correct
59 Correct 528 ms 84084 KB Output is correct
60 Correct 555 ms 84552 KB Output is correct
61 Correct 507 ms 84680 KB Output is correct
62 Correct 712 ms 79856 KB Output is correct
63 Correct 494 ms 58092 KB Output is correct
64 Correct 509 ms 58088 KB Output is correct
65 Correct 514 ms 58600 KB Output is correct
66 Correct 602 ms 57840 KB Output is correct
67 Correct 448 ms 51180 KB Output is correct
68 Correct 605 ms 57324 KB Output is correct
69 Correct 617 ms 77040 KB Output is correct
70 Correct 486 ms 71736 KB Output is correct
71 Correct 666 ms 74600 KB Output is correct
72 Correct 663 ms 75140 KB Output is correct