fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. struct Point {
  7.     ll x, y, w;
  8.     int L, R; // chỉ số nén trên trục Y
  9. };
  10.  
  11. const int MAXN = 100000;
  12. const int MAXM = 2 * MAXN + 5;
  13.  
  14. ll seg[4*MAXM], lazy[4*MAXM];
  15.  
  16. void push(int id) {
  17.     if (lazy[id] != 0) {
  18.         ll v = lazy[id];
  19.         seg[id<<1] += v; lazy[id<<1] += v;
  20.         seg[id<<1|1] += v; lazy[id<<1|1] += v;
  21.         lazy[id] = 0;
  22.     }
  23. }
  24.  
  25. void update(int id, int l, int r, int u, int v, ll val) {
  26.     if (v < l || r < u) return;
  27.     if (u <= l && r <= v) {
  28.         seg[id] += val;
  29.         lazy[id] += val;
  30.         return;
  31.     }
  32.     push(id);
  33.     int mid = (l + r) >> 1;
  34.     update(id<<1, l, mid, u, v, val);
  35.     update(id<<1|1, mid+1, r, u, v, val);
  36.     seg[id] = max(seg[id<<1], seg[id<<1|1]);
  37. }
  38.  
  39. int main() {
  40.     ios::sync_with_stdio(false);
  41.     cin.tie(nullptr);
  42.  
  43.     int N;
  44.     ll W, H;
  45.     if (!(cin >> N >> W >> H)) return 0;
  46.  
  47.     vector<Point> a(N);
  48.     vector<ll> ys;
  49.     ys.reserve(2 * N);
  50.  
  51.     for (int i = 0; i < N; ++i) {
  52.         cin >> a[i].x >> a[i].y >> a[i].w;
  53.         ll L = a[i].y - H;
  54.         ll R = a[i].y;
  55.         ys.push_back(L);
  56.         ys.push_back(R);
  57.         a[i].y = R; // lưu lại cho rõ ràng, L sẽ nén sau
  58.     }
  59.  
  60.     sort(ys.begin(), ys.end());
  61.     ys.erase(unique(ys.begin(), ys.end()), ys.end());
  62.     int M = ys.size();
  63.  
  64.     for (int i = 0; i < N; ++i) {
  65.         ll Lval = a[i].y - H;
  66.         ll Rval = a[i].y;
  67.         a[i].L = lower_bound(ys.begin(), ys.end(), Lval) - ys.begin();
  68.         a[i].R = lower_bound(ys.begin(), ys.end(), Rval) - ys.begin();
  69.     }
  70.  
  71.     sort(a.begin(), a.end(), [](const Point &p, const Point &q) {
  72.         return p.x < q.x;
  73.     });
  74.  
  75.     ll ans = 0;
  76.     int l = 0;
  77.  
  78.     for (int r = 0; r < N; ++r) {
  79.         // thêm điểm r
  80.         update(1, 0, M-1, a[r].L, a[r].R, a[r].w);
  81.  
  82.         // đảm bảo chiều rộng theo x không vượt W
  83.         while (l <= r && a[r].x - a[l].x > W) {
  84.             update(1, 0, M-1, a[l].L, a[l].R, -a[l].w);
  85.             ++l;
  86.         }
  87.  
  88.         ans = max(ans, seg[1]); // seg[1] là max toàn cục
  89.     }
  90.  
  91.     cout << ans << '\n';
  92.     return 0;
  93. }
  94.  
Success #stdin #stdout 0.01s 5548KB
comments (?)
stdin 
5 3 2
0 2 7
1 0 5
1 3 5
2 1 3
3 1 9
stdout 
24
https://ideone.com/nZDf0v
language:
C++14 (gcc 8.3)
created:
11 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!