oj.uz

답안 #974132

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
974132 2024-05-02T21:15:39 Z Ooops_sorry 수확 (JOI20_harvest) C++14
20 / 100
 770 ms 200372 KB 
#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];
 
void zhfs(int v) {
  sz[v] = mas[v].size();
  for (auto [u, c] : g[v]) {
    if (!on_cycle[u]) {
      dep[u] = dep[v] + c;
      sz[v] += sz[u];
      zhfs(u);
    }
  }
}
 
vector<ll> st[N];
 
void dfs(int v) {
  for (auto i : mas[v]) {
    st[v].pb(i + dep[v]);
  }
  for (auto [u, c] : g[v]) {
    if (!on_cycle[u]) {
      dfs(u);
      if (st[u].size() > st[v].size()) {
        swap(st[u], st[v]);
      }
    }
  }
  for (auto [u, c] : g[v]) {
    if (!on_cycle[u]) {
      for (int i : st[u]) {
        st[v].pb(i);
      }
    }
  }
  if (!on_cycle[v]) {
    for (auto [t, i] : query[v]) {
      ans[i] = st[v].size();
    }
  }
}
 
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]) {
      zhfs(i);
      dfs(i);
    }
  }
  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; 
}

Compilation message

harvest.cpp: In function 'void zhfs(long long int)':
harvest.cpp:66:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |   for (auto [u, c] : g[v]) {
      |             ^
harvest.cpp: In function 'void dfs(long long int)':
harvest.cpp:81:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |   for (auto [u, c] : g[v]) {
      |             ^
harvest.cpp:89:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |   for (auto [u, c] : g[v]) {
      |             ^
harvest.cpp:97:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |     for (auto [t, i] : query[v]) {
      |               ^
harvest.cpp: In function 'int main()':
harvest.cpp:130: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]
  130 |   while (j < b.size() && b[j] < a[0]) {
      |          ~~^~~~~~~~~~
harvest.cpp:135: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]
  135 |     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:140: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]
  140 |   assert(j == b.size());
      |          ~~^~~~~~~~~~~
harvest.cpp:186:25: warning: unused variable 'v' [-Wunused-variable]
  186 |       int u = cycle[i], v = cycle[(i + 1) % sz];
      |                         ^
harvest.cpp:197:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  197 |       for (auto [t, ind] : query[v]) {
      |                 ^
harvest.cpp:208:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  208 |     for (auto [t, arr] : mp) {
      |               ^
harvest.cpp:209: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]
  209 |       while (ind < u.size() && u[ind] <= t) {
      |              ~~~~^~~~~~~~~~
harvest.cpp:216:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  216 |       for (auto [pos, i] : arr) {
      |                 ^
harvest.cpp:237:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  237 |       for (auto [t, ind] : query[v]) {
      |                 ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 23384 KB Output is correct
2 Correct 12 ms 25528 KB Output is correct
3 Correct 14 ms 26040 KB Output is correct
4 Incorrect 13 ms 23896 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 507 ms 52340 KB Output is correct
2 Correct 383 ms 42736 KB Output is correct
3 Correct 482 ms 176908 KB Output is correct
4 Correct 661 ms 200372 KB Output is correct
5 Correct 377 ms 79000 KB Output is correct
6 Correct 369 ms 78936 KB Output is correct
7 Correct 324 ms 42284 KB Output is correct
8 Correct 322 ms 41272 KB Output is correct
9 Correct 686 ms 70272 KB Output is correct
10 Correct 525 ms 74860 KB Output is correct
11 Correct 770 ms 76108 KB Output is correct
12 Correct 737 ms 76340 KB Output is correct
13 Correct 747 ms 76304 KB Output is correct
14 Correct 543 ms 74704 KB Output is correct
15 Correct 566 ms 64560 KB Output is correct
16 Correct 353 ms 64912 KB Output is correct
17 Correct 367 ms 64804 KB Output is correct
18 Correct 291 ms 42488 KB Output is correct
19 Correct 310 ms 42184 KB Output is correct
20 Correct 358 ms 49916 KB Output is correct

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 23384 KB Output is correct
2 Correct 12 ms 25528 KB Output is correct
3 Correct 14 ms 26040 KB Output is correct
4 Incorrect 13 ms 23896 KB Output isn't correct
5 Halted 0 ms 0 KB -