fork download
copy 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. using namespace std;// anh VBuongw BẮT EM NÔP THƯ Ạ , TẠIH BẠN Ở NHÀ 
  4.  
  5. using ll = long long;
  6.  
  7. const int MAXN = 200000 + 5;
  8. const int KMAX = 10;            // k <= 10
  9. const int TOPSZ = KMAX + 1;     // lưu top 11 (k+1)
  10.  
  11. int T;
  12. int bpar[MAXN], H[MAXN], V[MAXN];
  13. ll sumVal[MAXN];
  14.  
  15. // topH[i][j]: j-th lớn nhất (0-based) của các h trên đường i->1, j < topSz[i]
  16. int topH[MAXN][TOPSZ];
  17. int topSz[MAXN];
  18.  
  19. int Q;
  20. int rq[MAXN], kq[MAXN];
  21. ll ans[MAXN];
  22.  
  23. int main(){
  24.     ios::sync_with_stdio(false);
  25.     cin.tie(nullptr);
  26.  
  27.     cin >> T;
  28.     // Node 1 là gốc
  29.     for(int i = 2; i <= T; ++i){
  30.         int b, h, v; cin >> b >> h >> v;
  31.         bpar[i] = b; H[i] = h; V[i] = v;
  32.     }
  33.  
  34.     // sumVal & topH
  35.     sumVal[1] = 0;
  36.     topSz[1] = 0;
  37.     for(int j = 0; j < TOPSZ; ++j) topH[1][j] = -1;
  38.  
  39.     for(int i = 2; i <= T; ++i){
  40.         int p = bpar[i];
  41.         sumVal[i] = sumVal[p] + V[i];
  42.  
  43.         // copy top của cha vào buffer
  44.         int s = topSz[p];
  45.         int buf[TOPSZ + 1]; // cho phép dư 1 để chèn rồi cắt xuống 11
  46.         for(int j = 0; j < s; ++j) buf[j] = topH[p][j];
  47.  
  48.         // chèn H[i] vào buf sao cho giảm dần
  49.         int pos = 0;
  50.         while(pos < s && buf[pos] >= H[i]) ++pos;
  51.         // dịch sang phải
  52.         for(int j = min(s, TOPSZ); j > pos; --j) buf[j] = buf[j-1];
  53.         buf[pos] = H[i];
  54.  
  55.         int ns = min(s + 1, TOPSZ);
  56.         for(int j = 0; j < ns; ++j) topH[i][j] = buf[j];
  57.         topSz[i] = ns;
  58.         // phần còn lại (nếu có) không cần set
  59.     }
  60.  
  61.     cin >> Q;
  62.     vector<pair<int,int>> bucketQ[KMAX+1]; // (r, id)
  63.     for(int i = 0; i < Q; ++i){
  64.         int r, k; cin >> r >> k;
  65.         rq[i] = r; kq[i] = k;
  66.         bucketQ[k].push_back({r, i});
  67.     }
  68.  
  69.     // Xử lý cho từng k
  70.     vector<pair<int,ll>> items; // (f_k(i), sumVal[i])
  71.     items.reserve(T);
  72.  
  73.     for(int k = 0; k <= KMAX; ++k){
  74.         // chuẩn bị items cho k
  75.         items.clear();
  76.         items.reserve(T);
  77.         for(int i = 1; i <= T; ++i){
  78.             int fk = -1;
  79.             if(topSz[i] > k) fk = topH[i][k]; // (k+1)-th lớn nhất là index k
  80.             items.push_back({fk, sumVal[i]});
  81.         }
  82.         sort(items.begin(), items.end(), [](const auto& a, const auto& b){
  83.             if(a.first != b.first) return a.first < b.first;
  84.             return a.second < b.second; // tie-break không quan trọng
  85.         });
  86.  
  87.         // xử lý các truy vấn có đúng k
  88.         auto &B = bucketQ[k];
  89.         if(B.empty()) continue;
  90.         sort(B.begin(), B.end()); // sort theo r tăng
  91.  
  92.         ll curMax = 0; // v >= 0 => sumVal >= 0, nên init = 0 là đúng
  93.         int ptr = 0;
  94.         for(auto [r, id] : B){
  95.             while(ptr < (int)items.size() && items[ptr].first <= r){
  96.                 curMax = max(curMax, items[ptr].second);
  97.                 ++ptr;
  98.             }
  99.             ans[id] = curMax;
  100.         }
  101.     }
  102.  
  103.     // in kết quả
  104.     for(int i = 0; i < Q; ++i) cout << ans[i] << "\n";
  105.     return 0;
  106. }
  107.  
Success #stdin #stdout 0.01s 7672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kcG69L
language:
C++ 4.3.2 (gcc-4.3.2)
created:
19 days 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!