Submission #216901

#	Time	Username	Problem	Language	Result	Execution time	Memory
216901		rama_pang	Harvest (JOI20_harvest)	C++14	100 / 100	766 ms	95780 KiB

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 (stderr)

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 / 5
• Subtask 2: 20 / 20
• Subtask 3: 75 / 75