Submission #960696

#TimeUsernameProblemLanguageResultExecution timeMemory
960696PringHarvest (JOI20_harvest)C++17
0 / 100
5049 ms107384 KiB
#include <bits/stdc++.h> #include <bits/extc++.h> using namespace std; using namespace __gnu_pbds; #ifdef MIKU string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m"; #define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x) void dout() { cout << dbrs << endl; } template <typename T, typename ...U> void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); } #else #define debug(...) 39 #endif // #define int long long #define int __int128_t #define ll __int128_t #define lll __int128_t #define fs first #define sc second #define mp make_pair #define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++) // using ll = long long; // using lll = __int128_t; typedef pair<int, int> pii; typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> PBDS_TREE; const int MXN = 200005; int n, m, L, adf, a[MXN], b[MXN], q, qid[MXN]; ll qt[MXN]; int p[MXN], pt[MXN]; ll ans[MXN]; vector<pii> edge[MXN]; vector<int> qry[MXN]; bitset<MXN> vis; PBDS_TREE tr[MXN]; ll lz[MXN]; // __int128_t READ() { // long long x; // cin >> x; // return x; // } istream &operator>>(istream &ss, __int128_t &x) { long long y; ss >> y; x = y; return ss; } ostream &operator<<(ostream &ss, __int128_t x) { long long y = x; ss << y; return ss; } struct VSET { bitset<MXN> b; vector<int> v; void init() { b.reset(); v.clear(); } void insert(int x) { if (b[x]) return; b[x] = true; v.push_back(x); } void clear() { for (auto &i : v) b[i] = false; v.clear(); } } sr; struct BIT { int n; lll val[MXN]; void init(int _n) { n = _n; fill(val, val + n, 0); } void modify(int id, lll v) { for (id++; id <= n; id += (id & -id)) val[id] += v; } lll query(int id) { ll ans = 0; for (; id > 0; id -= (id & -id)) ans += val[id]; return ans; } } B; void PUT_TREE() { FOR(i, 0, m) { int pp = lower_bound(a, a + n, b[i]) - a - 1; if (pp == -1) pp += n; int x = (b[i] - a[pp] + L) % L; debug(i, pp, x); tr[pp].insert(x); } } void GET_P() { vector<pii> v; FOR(i, 0, n) v.push_back(mp(a[i], i)); FOR(i, 0, n) v.push_back(mp(a[i] + L, i)); FOR(i, 0, n) { auto pp = prev(lower_bound(v.begin(), v.end(), mp(a[i] + L - adf % L, MXN))); p[i] = pp -> sc; pt[i] = adf / L * L + (a[i] + L - pp -> fs); debug(i, p[i], pt[i]); edge[p[i]].push_back(mp(pt[i], i)); } } void CALC_CYC(vector<ll> &v, vector<pair<ll, int>> &vq, ll C) { int n = v.size(), m = vq.size(); for (auto &[Q, aid] : vq) { for (auto &i : v) { if (Q - i < 0) continue; ans[aid] += (Q - i) / C + 1; } } // vector<lll> p(1, 0), pc(1, 0); // for (auto &i : v) { // p.push_back(p.back() + i); // pc.push_back(pc.back() + (C - i) % C); // } // B.init(n); // vector<pair<ll, int>> dist; // FOR(i, 0, n) dist.push_back(mp((v[i] ? v[i] - 1 : LLONG_MAX), i)); // FOR(i, 0, m) dist.push_back(mp(vq[i].fs % C, -i - 1)); // sort(dist.begin(), dist.end()); // for (auto &[t, id] : dist) { // if (id < 0) { // id = -id - 1; // auto [Q, aid] = vq[id]; // int s = lower_bound(v.begin(), v.end(), Q) - v.begin(); // if (s == 0) continue; // lll x = Q * s - p[s] - (pc[s] + t * s + B.query(s)); // debug(Q, s, aid, x / C); // ans[aid] += x / C + s; // } else { // B.modify(id, -C); // } // } } namespace JELLY { void MERGE(int rt, int id, ll w) { if (tr[rt].size() >= tr[id].size()) { for (auto i : tr[id]) tr[rt].insert(i + lz[id] + w - lz[rt]); } else { lz[id] += w; for (auto i : tr[rt]) tr[id].insert(i + lz[rt] - w); tr[rt].swap(tr[id]); swap(lz[rt], lz[id]); } tr[id].clear(); } void DFS(int id) { vis[id] = true; for (auto &[w, i] : edge[id]) { if (vis[i]) continue; DFS(i); } } void GET_SR() { FOR(i, 0, n) { if (vis[i]) continue; sr.insert(i); DFS(i); } } void CALC_MERGE(int id, bool f = true) { vis[id] = false; for (auto &[w, i] : edge[id]) { if (!vis[i]) continue; CALC_MERGE(i); MERGE(id, i, w); } if (f) { for (auto &i : qry[id]) { ll Q = qt[i] - lz[id]; int x = tr[id].order_of_key(Q + 1); debug(i, x); ans[i] += x; } } } void SOLVE(int rt) { debug(rt); CALC_MERGE(rt, false); vector<ll> v; for (auto i : tr[rt]) v.push_back(i + lz[rt]); vector<pair<ll, int>> vq; vector<int> cyc; cyc.push_back(rt); while (p[cyc.back()] != rt) { assert(cyc.size() < MXN); cyc.push_back(p[cyc.back()]); } int acc = 0; FOR(i, 0, cyc.size()) { debug(cyc[i]); for (auto &j : qry[cyc[i]]) { debug(j); vq.push_back(mp(qt[j] - acc, j)); } acc += pt[cyc[i]]; } CALC_CYC(v, vq, acc); } } void miku() { cin >> n >> m >> L >> adf; FOR(i, 0, n) cin >> a[i]; FOR(i, 0, m) cin >> b[i]; cin >> q; FOR(i, 0, q) { cin >> qid[i] >> qt[i]; qid[i]--; qry[qid[i]].push_back(i); } PUT_TREE(); GET_P(); JELLY::GET_SR(); for (auto &i : sr.v) { debug(i); JELLY::SOLVE(i); } FOR(i, 0, q) { assert(ans[i] <= LLONG_MAX); cout << (long long) ans[i] << '\n'; } } int32_t main() { cin.tie(0) -> sync_with_stdio(false); cin.exceptions(cin.failbit); miku(); return 0; }

Compilation message (stderr)

harvest.cpp: In function 'void PUT_TREE()':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:99:9: note: in expansion of macro 'debug'
   99 |         debug(i, pp, x);
      |         ^~~~~
harvest.cpp: In function 'void GET_P()':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:112:9: note: in expansion of macro 'debug'
  112 |         debug(i, p[i], pt[i]);
      |         ^~~~~
harvest.cpp: In function 'void CALC_CYC(std::vector<__int128>&, std::vector<std::pair<__int128, __int128> >&, __int128)':
harvest.cpp:118:9: warning: unused variable 'n' [-Wunused-variable]
  118 |     int n = v.size(), m = vq.size();
      |         ^
harvest.cpp:118:23: warning: unused variable 'm' [-Wunused-variable]
  118 |     int n = v.size(), m = vq.size();
      |                       ^
harvest.cpp: In function 'void JELLY::CALC_MERGE(__int128, bool)':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:187:17: note: in expansion of macro 'debug'
  187 |                 debug(i, x);
      |                 ^~~~~
harvest.cpp: In function 'void JELLY::SOLVE(__int128)':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:193:9: note: in expansion of macro 'debug'
  193 |         debug(rt);
      |         ^~~~~
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:206:13: note: in expansion of macro 'debug'
  206 |             debug(cyc[i]);
      |             ^~~~~
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:208:17: note: in expansion of macro 'debug'
  208 |                 debug(j);
      |                 ^~~~~
harvest.cpp: In function 'void miku()':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:231:9: note: in expansion of macro 'debug'
  231 |         debug(i);
      |         ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...