fork download
copy 
  1. /**
  2.  *    author:  orzvanh14 ( Độc cô cầu đặc )
  3.  *    created: 18.04.2026 03:56:02
  4. **/
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. #define int long long
  10. #define nn "\n"
  11. #define pb push_back
  12.  
  13. const int MAXN = 1e5 + 5;
  14.  
  15. struct Box {
  16.     int val, id;
  17.     bool operator<(const Box& other) const {
  18.         return val < other.val;
  19.     }
  20. };
  21.  
  22. struct Person {
  23.     int t, id;
  24.     bool operator<(const Person& other) const {
  25.         return t > other.t; // Sắp xếp theo t giảm dần
  26.     }
  27. };
  28.  
  29. int n, m;
  30. Box a[MAXN];
  31. Person queries[MAXN];
  32. int ans[MAXN];
  33.  
  34. // Segment Tree node: lưu (số lượng hộp, tổng số kẹo)
  35. pair<int, int> tree[4 * MAXN];
  36.  
  37. void update(int node, int l, int r, int idx, int val) {
  38.     if (l == r) {
  39.         tree[node].first += 1;   // Tăng số lượng hộp thêm 1
  40.         tree[node].second += val; // Cộng dồn giá trị kẹo
  41.         return;
  42.     }
  43.     int mid = (l + r) / 2;
  44.     if (idx <= mid) update(2 * node, l, mid, idx, val);
  45.     else update(2 * node + 1, mid + 1, r, idx, val);
  46.  
  47.     tree[node].first = tree[2 * node].first + tree[2 * node + 1].first;
  48.     tree[node].second = tree[2 * node].second + tree[2 * node + 1].second;
  49. }
  50.  
  51. pair<int, int> query(int node, int l, int r, int ql, int qr) {
  52.     if (ql > r || qr < l) return {0, 0};
  53.     if (ql <= l && r <= qr) return tree[node];
  54.  
  55.     int mid = (l + r) / 2;
  56.     pair<int, int> left_res = query(2 * node, l, mid, ql, qr);
  57.     pair<int, int> right_res = query(2 * node + 1, mid + 1, r, ql, qr);
  58.  
  59.     return {left_res.first + right_res.first, left_res.second + right_res.second};
  60. }
  61.  
  62. signed main() {
  63.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  64.  
  65.     cin >> n;
  66.     for (int i = 1; i <= n; i++) {
  67.         cin >> a[i].val;
  68.         a[i].id = i;
  69.     }
  70.  
  71.     cin >> m;
  72.     for (int i = 1; i <= m; i++) {
  73.         cin >> queries[i].t;
  74.         queries[i].id = i;
  75.     }
  76.  
  77.     // Sắp xếp hộp kẹo theo lượng kẹo tăng dần
  78.     sort(a + 1, a + n + 1);
  79.  
  80.     // Sắp xếp người theo ngưỡng t giảm dần
  81.     sort(queries + 1, queries + m + 1);
  82.  
  83.     int box_ptr = n;
  84.  
  85.     for (int i = 1; i <= m; i++) {
  86.         int t_curr = queries[i].t;
  87.         int person_id = queries[i].id;
  88.  
  89.         // Đưa tất cả các hộp có số kẹo >= t_curr vào Segment Tree
  90.         while (box_ptr >= 1 && a[box_ptr].val >= t_curr) {
  91.             update(1, 1, n, box_ptr, a[box_ptr].val);
  92.             box_ptr--;
  93.         }
  94.  
  95.         // Lấy kết quả từ đoạn [box_ptr + 1, n]
  96.         pair<int, int> res = query(1, 1, n, box_ptr + 1, n);
  97.         int count_boxes = res.first;
  98.         int total_candies = res.second;
  99.  
  100.         // Tính số kẹo người này ăn được
  101.         ans[person_id] = total_candies - count_boxes * (t_curr - 1);
  102.     }
  103.  
  104.     // In kết quả theo thứ tự truy vấn ban đầu
  105.     for (int i = 1; i <= m; i++) {
  106.         cout << ans[i] << nn;
  107.     }
  108.  
  109.     return 0;
  110. }
Success #stdin #stdout 0.01s 7716KB
comments (?)
stdin
copy 
3
3 1 1
2
1 2
stdout
copy 
5
2
https://ideone.com/oLVtnp
language:
C++14 (gcc 8.3)
created:
1 day 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!