API tools faq
paste
Advertisement
fooker

P903G

fooker
Apr 2nd, 2024
706
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 17.06 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. const ll nmax = 1e9+7;
  6. const ll nmax2 = 998244353;
  7.  
  8. #include <ext/pb_ds/assoc_container.hpp>
  9. #include <ext/pb_ds/tree_policy.hpp>
  10. #include <ext/pb_ds/detail/standard_policies.hpp>
  11. using namespace __gnu_pbds;
  12. typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  13. typedef tree<std::pair<ll, ll>, null_type, less<std::pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set_pair;
  14.  
  15. struct mergesort_tree {
  16.     ll n;
  17.     struct node {
  18.         std::vector<ll> container;
  19.         std::vector<ll> prefix;
  20.         ll low;
  21.         ll high;
  22.     };
  23.  
  24.     std::vector<node> tree;
  25.  
  26.     std::vector<ll> merge (std::vector<ll> &left, std::vector<ll> &right) {
  27.         std::vector<ll> temp;
  28.         ll l = 0, r = 0;
  29.  
  30.         while ((l != left.size()) || (r != right.size())){
  31.             if (l == left.size()){
  32.                 temp.push_back(right[r++]);
  33.             } else if (r == right.size()){
  34.                 temp.push_back(left[l++]);
  35.             } else if (left[l] > right[r]) {
  36.                 temp.push_back(right[r++]);
  37.             } else {
  38.                 temp.push_back(left[l++]);
  39.             }
  40.         }
  41.  
  42.         return temp;
  43.     }
  44.  
  45.     std::vector<ll> pref_calc (std::vector<ll> &a) {
  46.         std::vector<ll> temp;
  47.  
  48.         ll sum = 0;
  49.         temp.push_back(sum);
  50.  
  51.         for (ll i = 0; i < a.size(); i++){
  52.             sum += a[i];
  53.             temp.push_back(sum);
  54.         }
  55.  
  56.         return temp;
  57.     }
  58.  
  59.     node combine(node n1, node n2){
  60.         node n3;
  61.        
  62.         n3.container = merge(n1.container, n2.container);
  63.         n3.prefix = pref_calc(n3.container);
  64.         n3.high = std::max(n1.high, n2.high);
  65.         n3.low = std::min(n1.low, n2.low);
  66.        
  67.         return n3;
  68.     }
  69.  
  70.     mergesort_tree (const std::vector<ll> &a) {
  71.         n = a.size();
  72.         tree.resize(4 * n + 5);
  73.         build_segment_tree(a, 1, 1, n);
  74.     }
  75.  
  76.     void build_segment_tree (const std::vector<ll> &a, ll v, ll l, ll r){
  77.         if (l == r){
  78.             tree[v].low = a[l];
  79.             tree[v].high = a[l];
  80.             tree[v].container.push_back(a[l]);
  81.  
  82.             tree[v].prefix.push_back(0);
  83.             tree[v].prefix.push_back(a[l]);
  84.             return;
  85.         }
  86.  
  87.         ll mid = (l + r) >> 1;
  88.        
  89.         build_segment_tree(a, 2 * v, l, mid);
  90.         build_segment_tree(a, 2 * v + 1, mid + 1, r);
  91.        
  92.         tree[v] = combine(tree[2 * v], tree[2 * v + 1]);
  93.     }
  94.  
  95.     ll range_query(ll v, ll l, ll r, ll tl, ll tr, ll val){
  96.         if (l > r or r < tl or l > tr) return 0;
  97.         if (tl <= l and r <= tr){
  98.             if (tree[v].low > val) return 0;
  99.            
  100.             // std::cout << l << ' ' << r << '\\n';
  101.  
  102.             // std::cout << \"heres the container for this range => \\n\";
  103.             // for (auto u: tree[v].container){
  104.             //     std::cout << u << ' ';
  105.             // }
  106.             // std::cout << '\\n';
  107.  
  108.             // std::cout << \"heres the prefix for this range => \\n\";
  109.             // for (auto u: tree[v].prefix){
  110.             //     std::cout << u << ' ';
  111.             // }
  112.             // std::cout << '\\n';
  113.  
  114.             ll l_ = 1, r_ = tree[v].container.size();
  115.             while (l_ < r_){
  116.                 ll mid_ = (l_ + r_ + 1) >> 1;
  117.                 if (tree[v].container[mid_ - 1] > val){
  118.                     r_ = mid_ - 1;
  119.                 } else {
  120.                     l_ = mid_;
  121.                 }
  122.             }
  123.  
  124.             // std::cout << l_ << '\\n';
  125.  
  126.             return tree[v].prefix[l_];
  127.         }
  128.  
  129.         ll mid = (l + r) >> 1;
  130.         return range_query(2 * v, l, mid, tl, tr, val) + range_query(2 * v + 1, mid + 1, r, tl, tr, val);
  131.     }
  132.  
  133.     ll range_query(ll l, ll r, ll val){
  134.         return range_query(1, 1, n, l, r, val);
  135.     }
  136. };
  137.  
  138. template<class T>
  139. constexpr T power(T a, ll b){
  140.     T res {1};
  141.     for (; b; b /= 2, a *= a){
  142.         if (b % 2){
  143.             res *= a;
  144.         }
  145.     }
  146.     return res;
  147. }
  148.  
  149. constexpr ll mul(ll a, ll b, ll p) {
  150.     ll res = a * b - (ll)(1.L * a * b / p) * p;
  151.     res %= p;
  152.     if (res < 0) {
  153.         res += p;
  154.     }
  155.     return res;
  156. }
  157.  
  158. template<ll P>
  159. struct modint {
  160.     ll x;
  161.     constexpr modint() : x {0} {}
  162.     constexpr modint(ll y) : x {norm(y % getmod())} {}
  163.  
  164.     static ll mod;
  165.     constexpr static ll getmod() {
  166.         if (P > 0) {
  167.             return P;
  168.         } else {
  169.             return mod;
  170.         }
  171.     }
  172.     constexpr static void setmod(ll newmod) {
  173.         mod = newmod;
  174.     }
  175.     constexpr ll norm(ll x) const {
  176.         if (x < 0) {
  177.             x += getmod();
  178.         }
  179.         if (x >= getmod()) {
  180.             x -= getmod();
  181.         }
  182.         return x;
  183.     }
  184.     constexpr ll val() const {
  185.         return x;
  186.     }
  187.  
  188.     constexpr modint operator-() const {
  189.         modint res;
  190.         res.x = norm(getmod() - x);
  191.         return res;
  192.     }
  193.     constexpr modint inv() const {
  194.         return power(*this, getmod() - 2);
  195.     }
  196.     constexpr modint &operator*=(modint rhs) & {
  197.         if (getmod() < (1ULL << 31)) {
  198.             x = x * rhs.x % int(getmod());
  199.         } else {
  200.             x = mul(x, rhs.x, getmod());
  201.         }
  202.         return *this;
  203.     }
  204.     constexpr modint &operator+=(modint rhs) & {
  205.         x = norm(x + rhs.x);
  206.         return *this;
  207.     }
  208.     constexpr modint &operator-=(modint rhs) & {
  209.         x = norm(x - rhs.x);
  210.         return *this;
  211.     }
  212.     constexpr modint &operator/=(modint rhs) & {
  213.         return *this *= rhs.inv();
  214.     }
  215.     friend constexpr modint operator*(modint lhs, modint rhs) {
  216.         modint res = lhs;
  217.         res *= rhs;
  218.         return res;
  219.     }
  220.     friend constexpr modint operator+(modint lhs, modint rhs) {
  221.         modint res = lhs;
  222.         res += rhs;
  223.         return res;
  224.     }
  225.     friend constexpr modint operator-(modint lhs, modint rhs) {
  226.         modint res = lhs;
  227.         res -= rhs;
  228.         return res;
  229.     }
  230.     friend constexpr modint operator/(modint lhs, modint rhs) {
  231.         modint res = lhs;
  232.         res /= rhs;
  233.         return res;
  234.     }
  235.     friend constexpr std::istream &operator>>(std::istream &is, modint &a) {
  236.         ll v;
  237.         is >> v;
  238.         a = modint(v);
  239.         return is;
  240.     }
  241.     friend constexpr std::ostream &operator<<(std::ostream &os, const modint &a) {
  242.         return os << a.val();
  243.     }
  244.     friend constexpr bool operator==(modint lhs, modint rhs ){
  245.         return lhs.val() == rhs.val();
  246.     }
  247.     friend constexpr bool operator!=(modint lhs, modint rhs) {
  248.         return lhs.val() != rhs.val();
  249.     }
  250. };
  251.  
  252. template<>
  253. ll modint<0>::mod = 1e9;
  254. using mm = modint<0>;
  255.  
  256. class DSU {
  257. public:
  258.     std::vector<ll> f, siz;
  259.     DSU(ll n) : f(n + 1), siz(n + 1, 1) {
  260.         std::iota(f.begin() + 1, f.end(), 1);
  261.     }
  262.     ll leader(ll x) {
  263.         while (x != f[x]) x = f[x] = f[f[x]];
  264.         return x;
  265.     }
  266.     bool same(ll x, ll y) {
  267.         return leader(x) == leader(y);
  268.     }
  269.     void merge(ll x, ll y) {
  270.         x = leader(x);
  271.         y = leader(y);
  272.         if (x == y) return;
  273.         siz[x] += siz[y];
  274.         f[y] = x;
  275.     }
  276.     ll size(ll x) {
  277.         return siz[leader(x)];
  278.     }
  279.     void print(ll n){
  280.         std::cout << "first nodes => ";
  281.         for (ll i = 1; i <= n; i++) std::cout << i << " \n"[i == n];
  282.         std::cout << "leader nodes => ";
  283.         for (ll i = 1; i <= n; i++) std::cout << leader(i) << " \n"[i == n];
  284.         std::cout << "size components => ";
  285.         for (ll i = 1; i <= n; i++) std::cout << siz[i] << " \n"[i == n];
  286.     }
  287. };
  288.  
  289. struct lazy_segment_tree {
  290.     ll n;
  291.     struct node {
  292.         ll minimum;
  293.         bool lazytag;
  294.     };
  295.  
  296.     std::vector<node> tree;
  297.  
  298.     node combine(node n1, node n2) {
  299.         node n3;
  300.         n3.minimum = std::min(n1.minimum, n2.minimum);
  301.         n3.lazytag = false;
  302.         return n3;
  303.     }
  304.  
  305.     lazy_segment_tree (const std::vector<ll> &a) {
  306.         n = a.size();
  307.         tree.resize(4 * n + 5);
  308.         build_segment_tree(a, 1, 1, n);
  309.     }
  310.  
  311.     void build_segment_tree(const std::vector<ll> &a, ll v, ll l, ll r) {
  312.         if (l == r){
  313.             tree[v].minimum = a[l];
  314.             tree[v].lazytag = false;
  315.             return;
  316.         }
  317.         ll mid = (l + r) >> 1;
  318.  
  319.         build_segment_tree(a, 2 * v, l, mid);
  320.         build_segment_tree(a, 2 * v + 1, mid + 1, r);
  321.  
  322.         tree[v] = combine(tree[2 * v], tree[2 * v + 1]);
  323.     }
  324.  
  325.     void lazypropogate(ll v, ll l, ll mid, ll r){
  326.         tree[v].lazytag = false;
  327.  
  328.         ll extra = tree[v].minimum - std::min(tree[2 * v].minimum, tree[2 * v + 1].minimum);
  329.         tree[2 * v].minimum += extra;
  330.         tree[2 * v + 1].minimum += extra;
  331.  
  332.         tree[2 * v].lazytag = true;
  333.         tree[2 * v + 1].lazytag = true;
  334.     }
  335.  
  336.     void range_update(ll v, ll l, ll r, ll tl, ll tr, ll val) {
  337.         if (l > r or r < tl or l > tr) return;
  338.         if (tl <= l and r <= tr){
  339.             tree[v].lazytag = true;
  340.             tree[v].minimum += val;
  341.             return ;
  342.         }
  343.         ll mid = (l + r) >> 1;
  344.         if (tree[v].lazytag) lazypropogate(v, l, mid, r);
  345.  
  346.         range_update(2 * v, l, mid, tl, tr, val);
  347.         range_update(2 * v + 1, mid + 1, r, tl, tr, val);
  348.  
  349.         tree[v] = combine(tree[2 * v], tree[2 * v + 1]);
  350.     }
  351.  
  352.     void range_update(ll l, ll r, ll val) {
  353.         range_update(1, 1, n, l, r, val);
  354.     }
  355.  
  356.     ll range_query(ll v, ll l, ll r, ll tl, ll tr) {
  357.         if (l > r or r < tl or l > tr) return LLONG_MAX;
  358.         if (tl <= l and r <= tr) {
  359.             return tree[v].minimum;
  360.         }
  361.         ll mid = (l + r) >> 1;
  362.         if (tree[v].lazytag) lazypropogate(v, l, mid, r);
  363.  
  364.         return std::min(tree[2 * v].minimum, tree[2 * v + 1].minimum);
  365.     }
  366.  
  367.     ll range_query(ll l, ll r){
  368.         return range_query(1, 1, n, l, r);
  369.     }
  370.  
  371.     void point_update(ll v, ll l, ll r, ll target, ll val) {
  372.         if (l == r){
  373.             tree[v].minimum += val;
  374.             return;
  375.         }
  376.         ll mid = (l + r) >> 1;
  377.         if (tree[v].lazytag) lazypropogate(v, l, mid, r);
  378.  
  379.         if (target <= mid) {
  380.             point_update(2 * v, l, mid, target, val);
  381.         } else {
  382.             point_update(2 * v + 1, mid + 1, r, target, val);
  383.         }
  384.         tree[v] = combine(tree[2 * v], tree[2 * v + 1]);
  385.     }
  386.  
  387.     void point_update(ll target, ll val) {
  388.         point_update(1, 1, n, target, val);
  389.     }
  390. };
  391.  
  392. // struct segment_tree {
  393. //     ll n;
  394. //     struct node {
  395. //         ll minimum;
  396. //     };
  397.  
  398. //     std::vector<node> tree;
  399.  
  400. //     node combine(node n1, node n2) {
  401. //         node n3;
  402. //         n3.minimum = std::min(n1.minimum, n2.minimum);
  403. //         return n3;
  404. //     }
  405.  
  406. //     segment_tree (const std::vector<ll> &a) {
  407. //         n = a.size();
  408. //         tree.resize(4 * n + 5);
  409. //         build_segment_tree(a, 1, 1, n);
  410. //     }
  411.  
  412. //     void build_segment_tree(const std::vector<ll> &a, ll v, ll l, ll r){
  413. //         if (l == r){
  414. //             tree[v].minimum = a[l];
  415. //             return;
  416. //         }
  417. //         ll mid = (l + r) >> 1;
  418. //         build_segment_tree(a, 2 * v, l, mid);
  419. //         build_segment_tree(a, 2 * v + 1, mid + 1, r);
  420.  
  421. //         tree[v] = combine(tree[2 * v], tree[2 * v + 1]);
  422. //     }
  423.  
  424. //     ll range_query(ll v, ll l, ll r, ll tl, ll tr) {
  425. //         if (l > r or r < tl or l > tr) return LLONG_MAX;
  426. //         if (tl <= l and r <= tr) {
  427. //             return tree[v].minimum;
  428. //         }
  429. //         ll mid = (l + r) >> 1;
  430. //         return std::min(range_query(2 * v, l, mid, tl, tr), range_query(2 * v + 1, mid + 1, r, tl, tr));
  431. //     }
  432.  
  433. //     ll range_query(ll l, ll r) {
  434. //         return range_query(1, 1, n, l, r);
  435. //     }
  436.  
  437. //     void point_update(ll v, ll l, ll r, ll target, ll val) {
  438. //         if (l == r){
  439. //             tree[v].minimum += val;
  440. //             return;
  441. //         }
  442. //         ll mid = (l + r) >> 1;
  443. //         if (target <= mid) {
  444. //             point_update(2 * v, l, mid, target, val);
  445. //         } else {
  446. //             point_update(2 * v + 1, mid + 1, r, target, val);
  447. //         }
  448. //         tree[v] = combine(tree[2 * v], tree[2 * v + 1]);
  449. //     }
  450.  
  451. //     void point_update(ll target, ll val) {
  452. //         point_update(1, 1, n, target, val);
  453. //     }
  454. // };
  455.  
  456. void solve() {
  457.     ll n, m, q;
  458.     std::cin >> n >> m >> q;
  459.  
  460.     std::vector<ll> a(n), b(n);
  461.     for (ll i = 1; i < n; i++){
  462.         std::cin >> a[i] >> b[i];
  463.     }
  464.  
  465.     std::vector<std::pair<ll, ll>> adj[n + 1];
  466.  
  467.     for (ll i = 1, x, y, z; i <= m; i++){
  468.         std::cin >> x >> y >> z;
  469.         adj[x].push_back({y, z});
  470.     }
  471.  
  472.     std::vector<ll> c(n + 1);
  473.     for (ll i = 1; i <= n; i++) c[i] = b[i - 1];
  474.  
  475.     lazy_segment_tree segtree(c);
  476.     for (ll i = 1; i <= n; i++){
  477.         if (i == 1){
  478.             for (auto &[u, cost]: adj[i]) {
  479.                 segtree.range_update(1, u, cost);
  480.             }
  481.         } else {
  482.             for (auto &[u, cost]: adj[i]) {
  483.                 segtree.range_update(u + 1, n, cost);
  484.             }
  485.         }
  486.     }
  487.  
  488.     std::vector<ll> ans(n + 1);
  489.     for (ll i = 1; i < n; i++) {
  490.         ans[i] = a[i];
  491.     }  
  492.  
  493.     ans[1] += segtree.range_query(1, n);
  494.  
  495.     for (ll i = 2; i <= n; i++) {
  496.         for (auto &[u, cost]: adj[i]) {
  497.             segtree.range_update(u + 1, n, -cost);
  498.             segtree.range_update(1, u, cost);
  499.         }
  500.  
  501.         ans[i] += segtree.range_query(1, n);
  502.     }
  503.  
  504.     lazy_segment_tree segtree2(ans);
  505.     std::cout << segtree2.range_query(1, n) << '\n';
  506.  
  507.     for (ll i = 1, x, y; i <= q; i++){
  508.         std::cin >> x >> y;
  509.  
  510.         segtree2.point_update(x, y - a[x]);
  511.         a[x] = y;
  512.         std::cout << segtree2.range_query(1, n) << '\n';
  513.     }
  514. }
  515.  
  516. void number_theory() {
  517. /*
  518.     // only linear sieve
  519. */  
  520.  
  521.     // ll lp[1000001];
  522.     // std::vector<ll> prs;
  523.     // for (ll i = 1; i < 1000001; i++) lp[i] = -1;
  524.     // for (ll i = 2; i <= 1000000; i++){
  525.     //     if (lp[i] == -1){
  526.     //         lp[i] = i;
  527.     //         prs.push_back(i);
  528.     //     }
  529.     //     for (ll j = 0; i * prs[j] <= 1000000; j++){
  530.     //         lp[i * prs[j]] = prs[j];
  531.     //         if (lp[i] == prs[j]) break;
  532.     //     }
  533.     // }
  534.  
  535. /*
  536.     // old number theory util funcs
  537. */
  538.  
  539.     // ll expo(ll x, ll y){
  540.     //     if (y == 0) return 1;
  541.     //     ll ans = expo(x, y / 2);
  542.     //     return (ans *= ans) *= (y % 2)*x + (!(y % 2));
  543.     // }
  544.     // ll binpow(ll x, ll y, ll z){
  545.     //     if (y == 0) return 1;
  546.     //     ll ans = binpow(x, y / 2, z);
  547.     //     return (((ans *= ans) %= z) *= (y % 2)*x + (!(y % 2))) %= z;
  548.     // }
  549.     // ll modinv(ll x, ll m){
  550.     //     return binpow(x, m-2, m);
  551.     // }
  552.     // ll phi(ll n){
  553.     //     ll result = n;
  554.     //     for (ll i = 2; i * i <= n; i++){
  555.     //         if (n % i == 0){
  556.     //             while (n % i == 0){
  557.     //                 n /= i;
  558.     //             }
  559.     //             result -= result / i;
  560.     //         }
  561.     //     }
  562.     //     if (n > 1) result -= result / n;
  563.     //     return result;
  564.     // }
  565.  
  566. /*
  567.     // mobius function + linear sieve
  568. */
  569.  
  570.     // std::function<ll(ll, ll)> gcd_ll = [&](ll x, ll y) {
  571.     //     return (y == 0) ? x : gcd_ll(y, x % y);
  572.     // };
  573.  
  574.     // ll lp[100001], mf[100001];
  575.     // std::vector<ll> prs;
  576.  
  577.     // lp[1] = 1;
  578.     // mf[1] = 1;
  579.  
  580.     // for (ll i = 2; i <= 100000; i++){
  581.     //     if (lp[i] == 0){
  582.     //         lp[i] = i;
  583.     //         mf[i] = -1;
  584.     //         prs.push_back(i);
  585.     //     }
  586.     //     for (ll j = 0; i * prs[j] <= 100000; j++){
  587.     //         lp[i * prs[j]] = prs[j];
  588.     //         if (gcd_ll(i, prs[j]) == 1) mf[i * prs[j]] = mf[i] * mf[prs[j]];
  589.     //         else mf[i * prs[j]] = 0;
  590.     //         if (lp[i] == prs[j]) break;
  591.     //     }
  592.     // }
  593. }
  594.  
  595. void iterative_segment_tree() {
  596.     ll n;
  597.     std::cin >> n;
  598.  
  599.     ll a[n + 1];
  600.     for (ll i = 1; i <= n; i++) std::cin >> a[i];
  601.  
  602.     ll tree_min[2 * n + 3], tree_max[2 * n + 3];
  603.     for (ll i = 1; i <= n; i++){
  604.         tree_min[n + i - 1] = a[i];
  605.         tree_max[n + i - 1] = a[i];
  606.     }
  607.    
  608.     for (ll i = n - 1; i > 0; i--){
  609.         tree_min[i] = std::min(tree_min[i << 1], tree_min[i << 1 | 1]);
  610.         tree_max[i] = std::max(tree_max[i << 1], tree_max[i << 1 | 1]);
  611.     }
  612.    
  613.     auto query_min = [&] (ll l_, ll r_) -> ll {
  614.         ll res = LLONG_MAX;
  615.         for (l_ += n - 1, r_ += n - 1; l_ < r_; l_ >>= 1, r_ >>= 1){
  616.         if (l_&1) res = std::min(res, tree_min[l_++]);
  617.             if (r_&1) res = std::min(res, tree_min[--r_]);
  618.         }
  619.         return res;
  620.     };
  621.    
  622.     auto query_max = [&] (ll l_, ll r_) -> ll {
  623.         ll res = 0;
  624.         for (l_ += n - 1, r_ += n - 1; l_ < r_; l_ >>= 1, r_ >>= 1){
  625.             if (l_&1) res = std::max(res, tree_max[l_++]);
  626.             if (r_&1) res = std::max(res, tree_max[--r_]);
  627.         }
  628.         return res;
  629.     };
  630. }
  631.  
  632. int main(){
  633.     std::ios_base::sync_with_stdio(false);
  634.     std::cin.tie(0);
  635.     std::cout.tie(0);
  636.  
  637.     int t = 1;
  638.     // std::cin >> t;
  639.     while(t--) {
  640.         solve();
  641.     }
  642. }
  643.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!