結果
問題 | No.2643 Many Range Sums Problems |
ユーザー |
![]() |
提出日時 | 2024-02-19 23:10:42 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 717 ms / 8,000 ms |
コード長 | 4,161 bytes |
コンパイル時間 | 3,179 ms |
コンパイル使用メモリ | 277,376 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-29 02:51:38 |
合計ジャッジ時間 | 13,464 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 34 |
ソースコード
#include<bits/stdc++.h>namespace {#pragma GCC diagnostic ignored "-Wunused-function"#include<atcoder/all>#pragma GCC diagnostic warning "-Wunused-function"using namespace std;using namespace atcoder;#define rep(i,n) for(int i = 0; i < (int)(n); i++)#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)#define all(x) begin(x), end(x)#define rall(x) rbegin(x), rend(x)template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }using ll = long long;using P = pair<int,int>;using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;// S : grouptemplate <class S, S (*op)(S, S), S (*e)(), S (*inv)(S)>struct weighted_union_find {public:weighted_union_find() : _n(0) {}explicit weighted_union_find(int n) : _n(n), parent_or_size(n, -1), weight(n, e()) {}int merge(int a, int b, S w) {// W(a->b) = Wa^-1 Wb = wassert(0 <= a && a < _n);assert(0 <= b && b < _n);int x = leader(a), y = leader(b);assert(x != y);if (-parent_or_size[x] < -parent_or_size[y]) {std::swap(x, y);std::swap(a, b);w = inv(w);}// Wa^-1 Wy Wb = w// Wy = Wa w Wb^-1weight[y] = op(op(weight[a], w), inv(weight[b]));parent_or_size[x] += parent_or_size[y];parent_or_size[y] = x;return x;}S diff(int a, int b) {// W(a->b) = Wa^-1 Wbint x = leader(a), y = leader(b);assert(x == y);return op(inv(weight[a]), weight[b]);}bool same(int a, int b) {assert(0 <= a && a < _n);assert(0 <= b && b < _n);return leader(a) == leader(b);}int leader(int a) {assert(0 <= a && a < _n);int pre = -1;while (parent_or_size[a] >= 0) {int na = parent_or_size[a];parent_or_size[a] = pre;pre = a;a = na;}S w = e();while (pre != -1) {w = op(w, weight[pre]);weight[pre] = w;int npre = parent_or_size[pre];parent_or_size[pre] = a;pre = npre;}return a;}int size(int a) {assert(0 <= a && a < _n);return -parent_or_size[leader(a)];}std::vector<std::vector<int>> groups() {std::vector<int> leader_buf(_n), group_size(_n);for (int i = 0; i < _n; i++) {leader_buf[i] = leader(i);group_size[leader_buf[i]]++;}std::vector<std::vector<int>> result(_n);for (int i = 0; i < _n; i++) {result[i].reserve(group_size[i]);}for (int i = 0; i < _n; i++) {result[leader_buf[i]].push_back(i);}result.erase(std::remove_if(result.begin(), result.end(),[&](const std::vector<int>& v) { return v.empty(); }),result.end());return result;}private:int _n;// root node: -1 * component size// otherwise: parentstd::vector<int> parent_or_size;std::vector<S> weight;};ll op(ll x, ll y) { return x + y; }ll e() { return 0; }ll inv(ll x) { return -x; }} int main() {ios::sync_with_stdio(false);cin.tie(0);int n, k;cin >> n >> k;VI r(n);VL x(n);rep(i, n) cin >> r[i] >> x[i];rep(i, n) {weighted_union_find<ll, op, e, inv> uf(n + 1);rep(j, n) if (j != i) uf.merge(j, r[j], x[j]);bool ans = [&]() {constexpr long long INF = 1002003004005006007;ll lb = -INF, ub = INF;int L1 = uf.leader(i), L2 = uf.leader(n);assert(L1 != L2);rep(j, n) {if (uf.same(j, j + 1)) {ll d = uf.diff(j, j + 1);if (d < 0 || d > k) return false;} else {int l1 = uf.leader(j), l2 = uf.leader(j + 1);if (l1 == L1) {assert(l2 == L2);ll v = -uf.diff(j, L1) + uf.diff(j+1, L2);chmax(lb, v);chmin(ub, k + v);} else {assert(l1 == L2 && l2 == L1);ll v = uf.diff(j, L2) - uf.diff(j + 1, L1);chmax(lb, v - k);chmin(ub, v);}}}return lb <= ub;}();cout << (ans ? "Yes\n" : "No\n");}}