제출 #974138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
974138		Ooops_sorry	수확 (JOI20_harvest)	C++14	100 / 100	868 ms	227136 KiB

harvest

#include<iostream>
#include<deque>
#include<algorithm>
#include<vector>
#include<map>
#include<random>
#include<time.h>
#include<cassert>
#include<chrono>
#include<set>
#include<unordered_set>
#include<array>
 
using namespace std;
 
#define ull unsigned long long
#define pb push_back
#define ld long double
#define ll long long
#define all(a) a.begin(), a.end()
#define int long long 
 
mt19937_64 rnd(51);
 
struct SegTree {
  vector<ll> t;
  SegTree(int n) {
    t.resize(4 * n);
  }
  void update(int v, int l, int r, int pos, ll val) {
    if (l == r) {
      t[v] += val;
      return;
    }
    int m = (l + r) / 2;
    if (pos <= m) {
      update(2 * v, l, m, pos, val);
    } else {
      update(2 * v + 1, m + 1, r, pos, val);
    }
    t[v] = t[v * 2] + t[v * 2 + 1];
  }
  ll get(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (tl == l && tr == r) {
      return t[v];
    }
    int tm = (tl + tr) / 2;
    return get(2 * v, tl, tm, l, min(r, tm)) + get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
  }
};
 
const int N = 2e5 + 10;
vector<int> mas[N];
 
vector<pair<int, int>> g[N];
bool on_cycle[N];
pair<int, int> go[N];
 
ll ans[N];
ll dep[N], sz[N];
vector<pair<ll, int>> query[N];

SegTree Tree(N);
vector<ll> dif;
 
void zhfs(int v) {
  for (auto i : mas[v]) {
    dif.pb(i + dep[v]);
  }
  sz[v] = mas[v].size();
  for (auto [u, c] : g[v]) {
    if (!on_cycle[u]) {
      dep[u] = dep[v] + c;
      zhfs(u);
      sz[v] += sz[u];
    }
  }
}
 
vector<ll> st[N];

void dfs(int v) {
  int best = -1;
  for (auto [u, c] : g[v]) {
    if (!on_cycle[u]) {
      if (best == -1 || sz[u] > sz[best]) {
        best = u;
      }
    }
  }
  for (auto [u, c] : g[v]) {
    if (!on_cycle[u] && best != u) {
      dfs(u);
      for (auto i : st[u]) {
        int j = lower_bound(all(dif), i) - dif.begin();
        Tree.update(1, 0, N - 1, j, -1);
      }
    }
  }
  if (best != -1) {
    dfs(best);
    swap(st[v], st[best]);
  }
  for (auto i : mas[v]) {
    int j = lower_bound(all(dif), i + dep[v]) - dif.begin();
    Tree.update(1, 0, N - 1, j, 1);
    st[v].pb(i + dep[v]);
  }
  for (auto [u, c] : g[v]) {
    if (!on_cycle[u]) {
      for (int i : st[u]) {
        st[v].pb(i);
        int j = lower_bound(all(dif), i) - dif.begin();
        Tree.update(1, 0, N - 1, j, 1);
      }
    }
  }
  if (!on_cycle[v]) {
    for (auto [t, i] : query[v]) {
      int j = upper_bound(all(dif), t + dep[v]) - dif.begin() - 1;
      ans[i] += Tree.get(1, 0, N - 1, 0, j);
    }
  }
}
 
signed main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif // LOCAL
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m, l, c;
  cin >> n >> m >> l >> c;
  int left = (c / l) * l;
  c %= l;
  vector<int> a(n), b(m);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < m; i++) {
    cin >> b[i];
  }
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int v;
    ll t;
    cin >> v >> t;
    v--;
    query[v].pb({t, i});
  }
  int j = 0;
  while (j < b.size() && b[j] < a[0]) {
    mas[n - 1].pb(b[j] + l - a[n - 1]);
    j++;
  }
  for (int i = 0; i < n; i++) {
    while (j < b.size() && (i == n - 1 || a[i + 1] > b[j])) {
      mas[i].pb(b[j] - a[i]);
      j++;
    }
  } 
  assert(j == b.size());
  for (int i = 0; i < n; i++) {
    a.pb(a[i] + l);
  }
  j = 0;
  for (int i = n; i < 2 * n; i++) {
    while (j + 1 < 2 * n && a[i] - a[j + 1] >= c) {
      j++;
    } 
    go[i % n] = {j % n, a[i] - a[j] + left};
    g[j % n].pb({i % n, a[i] - a[j] + left});
  }
  vector<bool> used(n);
  vector<deque<int>> cycles;
  for (int i = 0; i < n; i++) {
    if (!used[i]) {
      int j = i;
      map<int, int> here;
      deque<int> arr;
      while (!used[j]) {
        used[j] = 1;
        here[j] = 1;
        arr.pb(j);
        j = go[j].first;
      }
      if (here[j]) {
        while (arr.front() != j) {
          arr.pop_front();
        }
        cycles.pb(arr);
        for (int v : arr) {
          on_cycle[v] = 1;
        }
      }
    }
  }
  for (int i = 0; i < n; i++) {
    if (on_cycle[i]) {
      dif.clear();
      zhfs(i);
      sort(all(dif));
      dif.erase(unique(all(dif)), dif.end());
      dfs(i);
      for (int val : st[i]) {
        int j = lower_bound(all(dif), val) - dif.begin();
        Tree.update(1, 0, N - 1, j, -1);
      }
    }
  }
  for (auto cycle : cycles) {
    int sz = cycle.size();
    vector<ll> pr(sz + 1);
    for (int i = 0; i < sz; i++) {
      int u = cycle[i], v = cycle[(i + 1) % sz];
      pr[i + 1] = pr[i] + go[u].second;
    }
    vector<ll> u, rem;
    map<ll, vector<pair<int, int>>> mp;
    for (int i = 0; i < sz; i++) {
      int v = cycle[i];
      for (auto val : st[v]) {
        u.pb(val - pr[i]);
        rem.pb((val + pr.back() - pr[i]) % pr.back());
      }
      for (auto [t, ind] : query[v]) {
        mp[t - pr[i]].pb({ind, i});
      }
    }
    sort(all(u));
    sort(all(rem));
    rem.erase(unique(all(rem)), rem.end());
    int sz2 = rem.size();
    SegTree cnt2(sz2);
    int ind = 0;
    ll sum = 0;
    for (auto [t, arr] : mp) {
      while (ind < u.size() && u[ind] <= t) {
        sum += (u[ind] + pr.back()) / pr.back();
        int k = lower_bound(all(rem), (u[ind] + pr.back()) % pr.back()) - rem.begin();
        assert(rem[k] == (u[ind] + pr.back()) % pr.back());
        cnt2.update(1, 0, sz2 - 1, k, 1);
        ind++;
      }
      for (auto [pos, i] : arr) {
        int real_t = t + pr[i];
        int pos1 = upper_bound(all(rem), (real_t % pr.back()) - pr[i]) - rem.begin() - 1;
        int pos2 = lower_bound(all(rem), pr.back() - pr[i]) - rem.begin();
        ans[pos] += ind * (real_t / pr.back()) - sum;
        ans[pos] -= cnt2.get(1, 0, sz2 - 1, pos2, sz2 - 1);
        ans[pos] += cnt2.get(1, 0, sz2 - 1, 0, pos1);
        int pos3 = upper_bound(all(rem), real_t % pr.back() + pr.back() - pr[i]) - rem.begin() - 1;
        if (0 <= pos2 && pos2 <= pos3 && pos2 < sz2) {
          ans[pos] += cnt2.get(1, 0, sz2 - 1, pos2, pos3);
        }
      }
    }
    int sz1 = u.size();
    SegTree tr(sz1);
    for (int i = 0; i < sz; i++) {
      int v = cycle[i];
      for (auto val : st[v]) {
        int j = lower_bound(all(u), val - pr[i]) - u.begin();
        tr.update(1, 0, sz1 - 1, j, 1);
      }
      for (auto [t, ind] : query[v]) {
        int k = upper_bound(all(u), t - pr[i]) - u.begin() - 1;
        ans[ind] += tr.get(1, 0, sz1 - 1, 0, k);
      }
    }
  }
  for (int i = 0; i < q; i++) {
    cout << ans[i] << endl;
  }
  return 0; 
}

컴파일 시 표준 에러 (stderr) 메시지

harvest.cpp: In function 'void zhfs(long long int)':
harvest.cpp:72:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |   for (auto [u, c] : g[v]) {
      |             ^
harvest.cpp: In function 'void dfs(long long int)':
harvest.cpp:85:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |   for (auto [u, c] : g[v]) {
      |             ^
harvest.cpp:92:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |   for (auto [u, c] : g[v]) {
      |             ^
harvest.cpp:110:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  110 |   for (auto [u, c] : g[v]) {
      |             ^
harvest.cpp:120:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |     for (auto [t, i] : query[v]) {
      |               ^
harvest.cpp: In function 'int main()':
harvest.cpp:154:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   while (j < b.size() && b[j] < a[0]) {
      |          ~~^~~~~~~~~~
harvest.cpp:159:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     while (j < b.size() && (i == n - 1 || a[i + 1] > b[j])) {
      |            ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from harvest.cpp:8:
harvest.cpp:164:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |   assert(j == b.size());
      |          ~~^~~~~~~~~~~
harvest.cpp:217:25: warning: unused variable 'v' [-Wunused-variable]
  217 |       int u = cycle[i], v = cycle[(i + 1) % sz];
      |                         ^
harvest.cpp:228:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  228 |       for (auto [t, ind] : query[v]) {
      |                 ^
harvest.cpp:239:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  239 |     for (auto [t, arr] : mp) {
      |               ^
harvest.cpp:240:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  240 |       while (ind < u.size() && u[ind] <= t) {
      |              ~~~~^~~~~~~~~~
harvest.cpp:247:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  247 |       for (auto [pos, i] : arr) {
      |                 ^
harvest.cpp:268:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  268 |       for (auto [t, ind] : query[v]) {
      |                 ^

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