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

harvest

#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<long long> answer;
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
  vector<vector<int>> adj(N);
  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;
    adj[next_vertex[i]].emplace_back(i);
  }

  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]) {
      answer[q.second] = Treap::order_of_key(treap[cur], q.first);
    }
    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;

  answer.resize(Q, -1);
  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++) {
    cout << answer[i] << "\n";
  }
}

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