fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MaxN = 1e5 + 10;
  5.  
  6. int N, Q, id;
  7. vector <int> adj[MaxN];
  8. int health[MaxN], start[MaxN], finish[MaxN], node[MaxN];
  9.  
  10. class SegmentTree {
  11. private :
  12.     int minhealth[MaxN << 2], Count[MaxN << 2], poison[MaxN << 2];
  13. public:
  14.     #define mid ((l + r) >> 1)
  15.     void build(int k, int l, int r) {
  16.         if (l == r) {
  17.             poison[k] = 0;
  18.             minhealth[k] = health[node[l]];
  19.             Count[k] = 1;
  20.             return;
  21.         }
  22.  
  23.         build(2 * k, l, mid);
  24.         build((2 * k) + 1, mid + 1, r);
  25.  
  26.         minhealth[k] = min(minhealth[2 * k], minhealth[(2 * k) + 1]);
  27.         Count[k] = Count[2 * k] + Count[(2 * k) + 1];
  28.         poison[k] = 0;
  29.     }
  30.  
  31.     void lazy(int k, int l, int r) {
  32.         if (!poison[k])  return;
  33.         poison[l] += poison[k];     poison[r] += poison[k];
  34.         minhealth[l] -= poison[k];  minhealth[r] -= poison[k];
  35.         poison[k] = 0;
  36.     }
  37.  
  38.     void update(int k, int l, int r, int i, int j, int value) {
  39.         if (l > j || r < i) return;
  40.         if (i <= l && r <= j) {
  41.             poison[k] += value;
  42.             minhealth[k] -= value;
  43.             return;
  44.         }
  45.         lazy(k, 2 * k, (2 * k) + 1);
  46.  
  47.         update(2 * k, l, mid, i, j, value);
  48.         update((2 * k) + 1, mid + 1, r, i, j, value);
  49.         minhealth[k] = min(minhealth[2 * k], minhealth[(2 * k) + 1]);
  50.     }
  51.  
  52.     int get(int k, int l, int r, int i, int j) {
  53.         if (l > j || r < i) return 0;
  54.         lazy(k, 2 * k, (2 * k) + 1);
  55.         if (l == r) {
  56.             if (minhealth[k] > 0) return Count[k];
  57.             minhealth[k] = 2e9 + 7;
  58.             return Count[k] = 0;
  59.         }
  60.  
  61.         if (i <= l && r <= j) {
  62.             if (minhealth[k] <= 0) {
  63.                 get(2 * k, l, mid, i, j);
  64.                 get((2 * k) + 1, mid + 1, r, i, j);
  65.                 minhealth[k] = min(minhealth[2 * k], minhealth[(2 * k) + 1]);
  66.                 Count[k] = Count[2 * k] + Count[(2 * k) + 1];
  67.             }
  68.             return Count[k];
  69.         }
  70.  
  71.         int x = get(2 * k, l, mid, i, j);
  72.         int y = get((2 * k) + 1, mid + 1, r, i, j);
  73.         minhealth[k] = min(minhealth[2 * k], minhealth[(2 * k) + 1]);
  74.         Count[k] = Count[2 * k] + Count[(2 * k) + 1];
  75.         return x + y;
  76.     }
  77. } IT;
  78.  
  79. void Enter() {
  80.     cin >> N;
  81.     for (int i = 1; i <= N; ++i) {
  82.         int parent; cin >> health[i] >> parent;
  83.         adj[parent].push_back(i);
  84.     }
  85. }
  86.  
  87. void DFS(int u) {
  88.     node[id] = u; start[u] = id++;
  89.     for (int i = 0; i < adj[u].size(); ++i)
  90.         DFS(adj[u][i]);
  91.     finish[u] = id - 1;
  92. }
  93.  
  94. void Process() {
  95.     cin >> Q;
  96.     IT.build(1, 0, N);
  97.     while (Q--) {
  98.         int type; cin >> type;
  99.         if (type == 1) {
  100.             int A, X; cin >> A >> X;
  101.             IT.update(1, 0, N, start[A] + 1, finish[A], X);
  102.         } else {
  103.             int A; cin >> A;
  104.             cout << IT.get(1, 0, N, start[A] + 1, finish[A]) << "\n";
  105.         }
  106.     }
  107. }
  108.  
  109. int main() {
  110.   //  freopen("input.in", "r", stdin);
  111.     //freopen("output.out", "w", stdout);
  112.  
  113.     Enter();
  114.     DFS(0);
  115.     Process();
  116.  
  117.     return 0;
  118. }
  119.  
Success #stdin #stdout 0s 23840KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xaz6zy
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!