Submission #216981

#	Time	Username	Problem	Language	Result	Execution time	Memory
216981		IOrtroiii	Harvest (JOI20_harvest)	C++14	100 / 100	818 ms	139092 KiB

harvest

/*
5 3 20 6
0 4 8 12 16
2 11 14
9
4 1932
2 93787
1 89
5 98124798
1 2684
1 137598
3 2
3 8375
4 237
*/
#include <bits/stdc++.h>

#include <ext/pb_ds/tree_policy.hpp>

#include <ext/pb_ds/assoc_container.hpp>

using namespace std;

using namespace __gnu_pbds;

using ll = int64_t;
using ull = uint64_t;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
   ios_base::sync_with_stdio(false);
   int N, M; ll L, C;
   cin >> N >> M >> L >> C;
   vector<ll> A(N);
   for (int i = 0; i < N; ++i) cin >> A[i], A[i] = L - 1 - A[i]; // for convenience
   reverse(A.begin(), A.end());
   vector<int> nxt(N);
   vector<ll> dist(N);
   {
      for (int v = 0; v < N; ++v) {
         ll newA = (A[v] + C) % L;
         int z = lower_bound(A.begin(), A.end(), newA) - A.begin();
         if (z == N) {
            nxt[v] = 0;
            dist[v] = C + L + A[0] - newA;
         } else {
            nxt[v] = z;
            dist[v] = C + A[z] - newA;
         }
      }
   }

   vector<vector<ll>> adds(N);
   while (M--) {
      ll B;
      cin >> B;
      B = L - 1 - B;
      int z = lower_bound(A.begin(), A.end(), B) - A.begin();
      if (z == N) {
         adds[0].emplace_back(L + A[0] - B);
      } else {
         adds[z].emplace_back(A[z] - B);
      }
   }

   int Q;
   cin >> Q;
   vector<vector<pair<ll, int>>> qs(N);
   vector<ll> ans(Q);
   for (int i = 0; i < Q; ++i) {
      int v; ll T;
      cin >> v >> T;
      v = N - v;
      qs[v].emplace_back(T, i);
   }
   vector<bool> isRoot(N);
   vector<int> visited(N, 0);
   for (int i = 0; i < N; ++i) {
      int v = i;
      while (visited[v] == 0) {
         visited[v] = 1;
         v = nxt[v];
      }
      if (visited[v] == 1) isRoot[v] = true;
      v = i;
      while (visited[v] == 1) {
         visited[v] = 2;
         v = nxt[v];
      }
   }
   vector<vector<int>> adj(N);
   for (int v = 0; v < N; ++v) {
      if (!isRoot[v]) {
         adj[nxt[v]].emplace_back(v);
      }
   }
   vector<ll> distToRoot(N);
   vector<ordered_set<pair<ll, ull>>> vals(N);
   for (int i = 0; i < N; ++i) {
      if (!isRoot[i]) continue;
      function<void(int)> dfs1 = [&](int v) {
         for (int u : adj[v]) {
            distToRoot[u] = distToRoot[v] + dist[u];
            dfs1(u);
         }
      };
      dfs1(i);
      function<void(int)> dfs2 = [&](int v) {
         for (auto z : adds[v]) {
            vals[v].insert({distToRoot[v] + z, rng()});
         }
         for (int u : adj[v]) {
            dfs2(u);
            if (int(vals[v].size()) < int(vals[u].size())) {
               vals[v].swap(vals[u]);
            }
            for (auto z : vals[u]) {
               vals[v].insert(z);
            }
            vals[u] = {};
         }
         for (auto q : qs[v]) {
            ans[q.second] += vals[v].order_of_key({q.first + distToRoot[v], -1});
         }
      };
      dfs2(i);
      vector<pair<ll, int>> cur_qs;
      ll cycleLen = distToRoot[nxt[i]] + dist[i];
      int v = i;
      while (true) {
         for (auto q : qs[v]) {
            cur_qs.emplace_back(q.first - (cycleLen - distToRoot[v]), q.second); // must pass through removed edge
         }
         v = nxt[v];
         if (v == i) break;
      }
      for (auto z : vals[i]) cur_qs.emplace_back(z.first, -1);
      sort(cur_qs.begin(), cur_qs.end());
      ordered_set<pair<ll, ull>> st;
      ll subt = 0;
      for (auto q : cur_qs) {
         if (q.second == -1) {
            st.insert({q.first % cycleLen, rng()});
            subt += (q.first / cycleLen);
         } else {
            ans[q.second] += (ll(q.first / cycleLen) * ll(st.size()) + st.order_of_key({q.first % cycleLen, -1})) - subt;
         }
      }
   }
   for (int i = 0; i < Q; ++i) cout << ans[i] << "\n";
   return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 75 / 75