답안 #974130

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
974130 2024-05-02T21:12:00 Z Ooops_sorry 수확 (JOI20_harvest) C++14
0 / 100
5000 ms 208528 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]) {
      for (auto val : st[v]) {
        if (val - dep[v] <= t) {
          ans[i]++;
        }
      }
    }
  }
}
 
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[v].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 pos2 = upper_bound(all(rem), (real_t % pr.back()) - pr[i]) - rem.begin() - 1;
        int pos3 = lower_bound(all(rem), pr.back() - pr[i]) - rem.begin();
        for (int j = pos3; j < sz2; j++) {
          assert(rem[j] >= pr.back() - pr[i]);
        }
        ans[pos] += ind * (real_t / pr.back()) - sum;
        ans[pos] -= cnt2.get(1, 0, sz2 - 1, pos3, sz2 - 1);
        ans[pos] += cnt2.get(1, 0, sz2 - 1, 0, pos2);
        int pos4 = upper_bound(all(rem), real_t % pr.back() + pr.back() - pr[i]) - rem.begin() - 1;
        if (0 <= pos3 && pos3 <= pos4 && pos4 < sz2) {
          ans[pos] += cnt2.get(1, 0, sz2 - 1, pos3, pos4);
          
        }
      }
    }
    for (int i = 0; i < sz; i++) {
      int v = cycle[i];
      for (auto [t, ind] : query[v]) {
        for (int j = 0; j < sz; j++) {
          for (auto val : st[cycle[j]]) {
            if (val - pr[j] <= t - pr[i]) {
              //ans[ind] += t / pr.back() - (val - pr[j] + pr.back()) / pr.back();
              if (j <= i) {
                ans[ind]++;
              }
              /*
              if (pr.back() - pr[i] <= (val - pr[j] + pr.back()) % pr.back()) {
                ans[ind]--;
              }
              if ((val + pr[i] - pr[j] + pr.back()) % pr.back() <= t % pr.back()) {
                ans[ind]++;
              }*/
            }
          }
        } 
      }
    }
  }
  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:134: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]
  134 |   while (j < b.size() && b[j] < a[0]) {
      |          ~~^~~~~~~~~~
harvest.cpp:139: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]
  139 |     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:144: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]
  144 |   assert(j == b.size());
      |          ~~^~~~~~~~~~~
harvest.cpp:190:11: warning: unused variable 'u' [-Wunused-variable]
  190 |       int u = cycle[i], v = cycle[(i + 1) % sz];
      |           ^
harvest.cpp:201:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  201 |       for (auto [t, ind] : query[v]) {
      |                 ^
harvest.cpp:212:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  212 |     for (auto [t, arr] : mp) {
      |               ^
harvest.cpp:213: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]
  213 |       while (ind < u.size() && u[ind] <= t) {
      |              ~~~~^~~~~~~~~~
harvest.cpp:220:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  220 |       for (auto [pos, i] : arr) {
      |                 ^
harvest.cpp:239:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  239 |       for (auto [t, ind] : query[v]) {
      |                 ^
# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23384 KB Output is correct
2 Correct 12 ms 25528 KB Output is correct
3 Correct 24 ms 25780 KB Output is correct
4 Correct 13 ms 23644 KB Output is correct
5 Correct 14 ms 24148 KB Output is correct
6 Correct 14 ms 24156 KB Output is correct
7 Correct 16 ms 24152 KB Output is correct
8 Correct 10 ms 23644 KB Output is correct
9 Correct 10 ms 23644 KB Output is correct
10 Correct 10 ms 23640 KB Output is correct
11 Correct 10 ms 23644 KB Output is correct
12 Incorrect 56 ms 23900 KB Output isn't correct
13 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 938 ms 51896 KB Output is correct
2 Correct 407 ms 49020 KB Output is correct
3 Correct 497 ms 184320 KB Output is correct
4 Correct 1178 ms 208528 KB Output is correct
5 Correct 550 ms 85884 KB Output is correct
6 Correct 701 ms 86068 KB Output is correct
7 Correct 330 ms 48264 KB Output is correct
8 Correct 343 ms 48452 KB Output is correct
9 Execution timed out 5052 ms 74556 KB Time limit exceeded
10 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23384 KB Output is correct
2 Correct 12 ms 25528 KB Output is correct
3 Correct 24 ms 25780 KB Output is correct
4 Correct 13 ms 23644 KB Output is correct
5 Correct 14 ms 24148 KB Output is correct
6 Correct 14 ms 24156 KB Output is correct
7 Correct 16 ms 24152 KB Output is correct
8 Correct 10 ms 23644 KB Output is correct
9 Correct 10 ms 23644 KB Output is correct
10 Correct 10 ms 23640 KB Output is correct
11 Correct 10 ms 23644 KB Output is correct
12 Incorrect 56 ms 23900 KB Output isn't correct
13 Halted 0 ms 0 KB -