結果
問題 | No.2258 The Jikka Tree |
ユーザー | Jaehyun Koo |
提出日時 | 2023-06-04 21:41:26 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 3,210 ms / 4,000 ms |
コード長 | 3,972 bytes |
コンパイル時間 | 3,631 ms |
コンパイル使用メモリ | 205,488 KB |
実行使用メモリ | 105,728 KB |
最終ジャッジ日時 | 2023-08-28 08:30:57 |
合計ジャッジ時間 | 83,520 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
19,744 KB |
testcase_01 | AC | 5 ms
17,708 KB |
testcase_02 | AC | 6 ms
19,768 KB |
testcase_03 | AC | 24 ms
19,876 KB |
testcase_04 | AC | 19 ms
19,804 KB |
testcase_05 | AC | 24 ms
19,764 KB |
testcase_06 | AC | 25 ms
19,816 KB |
testcase_07 | AC | 25 ms
20,084 KB |
testcase_08 | AC | 19 ms
19,752 KB |
testcase_09 | AC | 44 ms
19,824 KB |
testcase_10 | AC | 39 ms
19,808 KB |
testcase_11 | AC | 34 ms
19,796 KB |
testcase_12 | AC | 15 ms
19,780 KB |
testcase_13 | AC | 17 ms
19,828 KB |
testcase_14 | AC | 22 ms
19,780 KB |
testcase_15 | AC | 24 ms
19,816 KB |
testcase_16 | AC | 16 ms
19,768 KB |
testcase_17 | AC | 26 ms
19,916 KB |
testcase_18 | AC | 21 ms
19,744 KB |
testcase_19 | AC | 21 ms
19,768 KB |
testcase_20 | AC | 141 ms
24,648 KB |
testcase_21 | AC | 219 ms
26,840 KB |
testcase_22 | AC | 263 ms
19,872 KB |
testcase_23 | AC | 239 ms
19,788 KB |
testcase_24 | AC | 188 ms
22,316 KB |
testcase_25 | AC | 553 ms
24,540 KB |
testcase_26 | AC | 717 ms
24,672 KB |
testcase_27 | AC | 573 ms
26,776 KB |
testcase_28 | AC | 765 ms
26,936 KB |
testcase_29 | AC | 824 ms
24,860 KB |
testcase_30 | AC | 808 ms
24,656 KB |
testcase_31 | AC | 388 ms
24,440 KB |
testcase_32 | AC | 287 ms
21,956 KB |
testcase_33 | AC | 400 ms
24,612 KB |
testcase_34 | AC | 2,584 ms
102,352 KB |
testcase_35 | AC | 575 ms
99,608 KB |
testcase_36 | AC | 1,065 ms
99,100 KB |
testcase_37 | AC | 1,168 ms
99,028 KB |
testcase_38 | AC | 1,108 ms
101,108 KB |
testcase_39 | AC | 1,727 ms
102,752 KB |
testcase_40 | AC | 482 ms
102,984 KB |
testcase_41 | AC | 2,747 ms
102,212 KB |
testcase_42 | AC | 2,961 ms
101,232 KB |
testcase_43 | AC | 2,410 ms
103,884 KB |
testcase_44 | AC | 492 ms
105,248 KB |
testcase_45 | AC | 1,038 ms
99,052 KB |
testcase_46 | AC | 1,158 ms
99,068 KB |
testcase_47 | AC | 1,104 ms
99,088 KB |
testcase_48 | AC | 508 ms
105,728 KB |
testcase_49 | AC | 640 ms
99,660 KB |
testcase_50 | AC | 1,121 ms
99,060 KB |
testcase_51 | AC | 1,301 ms
99,032 KB |
testcase_52 | AC | 1,411 ms
101,204 KB |
testcase_53 | AC | 2,116 ms
101,740 KB |
testcase_54 | AC | 2,233 ms
103,160 KB |
testcase_55 | AC | 3,210 ms
101,652 KB |
testcase_56 | AC | 3,007 ms
101,000 KB |
testcase_57 | AC | 1,723 ms
103,012 KB |
testcase_58 | AC | 524 ms
105,660 KB |
testcase_59 | AC | 1,734 ms
102,516 KB |
testcase_60 | AC | 735 ms
99,576 KB |
testcase_61 | AC | 1,249 ms
99,136 KB |
testcase_62 | AC | 1,215 ms
99,060 KB |
testcase_63 | AC | 985 ms
101,412 KB |
testcase_64 | AC | 1,014 ms
102,340 KB |
testcase_65 | AC | 2,511 ms
103,944 KB |
testcase_66 | AC | 2,810 ms
101,792 KB |
testcase_67 | AC | 2,829 ms
100,216 KB |
testcase_68 | AC | 796 ms
104,272 KB |
testcase_69 | AC | 753 ms
104,496 KB |
testcase_70 | AC | 958 ms
74,468 KB |
testcase_71 | AC | 279 ms
21,928 KB |
testcase_72 | AC | 146 ms
22,380 KB |
testcase_73 | AC | 149 ms
24,912 KB |
testcase_74 | AC | 187 ms
27,304 KB |
testcase_75 | AC | 324 ms
104,388 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using lint = long long; using pi = array<lint, 2>; #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() const int MAXN = 150005; const int MAXT = 4000000; struct node { int l, r; lint sum; int cnt; lint eval(lint k) { return sum + k * cnt; } } tree[MAXT]; int p; int newnode() { return ++p; } void pull(int p) { tree[p].sum = tree[tree[p].l].sum + tree[tree[p].r].sum; tree[p].cnt = tree[tree[p].l].cnt + tree[tree[p].r].cnt; } void init(int s, int e, int p) { if (s == e) { return; } int m = (s + e) / 2; tree[p].l = newnode(); tree[p].r = newnode(); init(s, m, tree[p].l); init(m + 1, e, tree[p].r); } void update(int pos, int s, int e, int r1, int r2, int v) { if (s == e) { tree[r2] = tree[r1]; tree[r2].sum += v; tree[r2].cnt += 1; return; } int m = (s + e) / 2; if (pos <= m) { tree[r2].l = newnode(); tree[r2].r = tree[r1].r; update(pos, s, m, tree[r1].l, tree[r2].l, v); } else { tree[r2].l = tree[r1].l; tree[r2].r = newnode(); update(pos, m + 1, e, tree[r1].r, tree[r2].r, v); } pull(r2); } vector<int> gph[MAXN]; int din[MAXN], dout[MAXN], par[18][MAXN], dep[MAXN], rev[MAXN], piv; void dfs(int x, int p) { din[x] = piv++; rev[din[x]] = x; for (auto &y : gph[x]) { if (y != p) { par[0][y] = x; dep[y] = dep[x] + 1; dfs(y, x); } } dout[x] = piv; } bool lessHalf(pi sum, lint tot) { if (sum[0] * 2 < tot) return true; if (sum[0] * 2 == tot && sum[1] == 0) return true; return false; } int get_med(int s, int e, int p1, int p2, int k, int t, pi curSum, lint tot) { if (s == e) return s; int m = (s + e) / 2; pi cmpSum = curSum; cmpSum[0] += tree[tree[p2].l].eval(k) - tree[tree[p1].l].eval(k); cmpSum[1] += (s <= t && t <= m ? 1 : 0); if (lessHalf(cmpSum, tot)) { return get_med(m + 1, e, tree[p1].r, tree[p2].r, k, t, cmpSum, tot); } return get_med(s, m, tree[p1].l, tree[p2].l, k, t, curSum, tot); } pi operator+(const pi &a, const pi &b) { return pi{a[0] + b[0], a[1] + b[1]}; } pi get_sum(int s, int e, int ps, int pe, int p1, int p2, int k, int t) { if (e < ps || pe < s) return pi{0, 0}; if (s <= ps && pe <= e) { lint sum = tree[p2].eval(k) - tree[p1].eval(k); return pi{sum, ps <= t && t <= pe}; } int pm = (ps + pe) / 2; return get_sum(s, e, ps, pm, tree[p1].l, tree[p2].l, k, t) + get_sum(s, e, pm + 1, pe, tree[p1].r, tree[p2].r, k, t); } int n; lint asum[MAXN]; vector<int> root; int query(int l, int r, int k, int d) { // cout << l << " " << r + 1 << " " << k << " " << d << "\n"; lint tot = asum[r + 1] - asum[l] + 1ll * (r - l + 1) * k; int v = get_med(0, n - 1, root[l], root[r + 1], k, din[d], pi{0, 0}, tot); v = rev[v]; auto sum = get_sum(din[v], dout[v] - 1, 0, n - 1, root[l], root[r + 1], k, din[d]); if (!lessHalf(sum, tot)) return v; for (int i = 17; i >= 0; i--) { if (dep[v] >= (1 >> i)) { int anc = par[i][v]; auto sum = get_sum(din[anc], dout[anc] - 1, 0, n - 1, root[l], root[r + 1], k, din[d]); if (lessHalf(sum, tot)) v = par[i][v]; } } return par[0][v]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; gph[u].push_back(v); gph[v].push_back(u); } dfs(0, -1); for (int i = 1; i < 18; i++) { for (int j = 0; j < n; j++) { par[i][j] = par[i - 1][par[i - 1][j]]; } } vector<int> a(n); for (auto &x : a) cin >> x; root.resize(n + 1); root[0] = newnode(); init(0, n - 1, root[0]); for (int i = 1; i <= n; i++) { root[i] = newnode(); update(din[i - 1], 0, n - 1, root[i - 1], root[i], a[i - 1]); asum[i] = asum[i - 1] + a[i - 1]; } int q; cin >> q; lint S = 0; while (q--) { lint a, b, z, d; cin >> a >> b >> z >> d; a += S; b += S * 2; z += (__int128)S * S % 150001; a %= n; b %= n; z %= 150001; if (a > b) swap(a, b); int ans = query(a, b, z, d); cout << ans << "\n"; S += ans; } }