fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. struct Event {
  7.     int y1, y2; // đoạn [y1, y2] (theo chỉ số đã nén)
  8.     ll v;       // +wi hoặc -wi
  9. };
  10.  
  11. struct SegTree {
  12.     int n;
  13.     vector<ll> mx, lazy;
  14.  
  15.     SegTree(int n = 0) { init(n); }
  16.  
  17.     void init(int n_) {
  18.         n = n_;
  19.         mx.assign(4 * n + 5, 0);
  20.         lazy.assign(4 * n + 5, 0);
  21.     }
  22.  
  23.     void push(int id) {
  24.         if (lazy[id] == 0) return;
  25.         ll v = lazy[id];
  26.         int L = id << 1, R = L | 1;
  27.         mx[L] += v; lazy[L] += v;
  28.         mx[R] += v; lazy[R] += v;
  29.         lazy[id] = 0;
  30.     }
  31.  
  32.     void upd(int id, int l, int r, int u, int v, ll val) {
  33.         if (u > r || v < l) return;
  34.         if (u <= l && r <= v) {
  35.             mx[id] += val;
  36.             lazy[id] += val;
  37.             return;
  38.         }
  39.         push(id);
  40.         int mid = (l + r) >> 1;
  41.         upd(id << 1, l, mid, u, v, val);
  42.         upd(id << 1 | 1, mid + 1, r, u, v, val);
  43.         mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
  44.     }
  45.  
  46.     void upd(int l, int r, ll val) {
  47.         if (l > r) return;
  48.         upd(1, 0, n - 1, l, r, val);
  49.     }
  50.  
  51.     ll getMax() const {
  52.         return mx[1];
  53.     }
  54. };
  55.  
  56. int main() {
  57.     ios::sync_with_stdio(false);
  58.     cin.tie(nullptr);
  59.  
  60.     int N;
  61.     ll W, H;
  62.     if (!(cin >> N >> W >> H)) return 0;
  63.     --H; --W;
  64.  
  65.     vector<ll> xi(N), yi(N), wi(N);
  66.     vector<ll> xs, ys;
  67.     xs.reserve(2 * N + 5);
  68.     ys.reserve(2 * N + 5);
  69.  
  70.     for (int i = 0; i < N; ++i) {
  71.         cin >> xi[i] >> yi[i] >> wi[i];
  72.  
  73.         ll lx = xi[i] - W;
  74.         ll rx = xi[i];
  75.         ll ly = yi[i] - H;
  76.         ll ry = yi[i];
  77.  
  78.         // lưu lại các biên để ép tọa độ
  79.         xs.push_back(lx);
  80.         xs.push_back(rx + 1); // +1 để làm biên phải mở
  81.         ys.push_back(ly);
  82.         ys.push_back(ry + 1);
  83.  
  84.         // tiện thì ghi đè lại luôn
  85.         xi[i] = lx;
  86.         yi[i] = ly;
  87.         // ta sẽ dùng (lx, rx, ly, ry) từ các biến tạm sau
  88.     }
  89.  
  90.     // ép tọa độ X
  91.     sort(xs.begin(), xs.end());
  92.     xs.erase(unique(xs.begin(), xs.end()), xs.end());
  93.     int nx = xs.size();
  94.  
  95.     // ép tọa độ Y
  96.     sort(ys.begin(), ys.end());
  97.     ys.erase(unique(ys.begin(), ys.end()), ys.end());
  98.     int ny = (int)ys.size() - 1; // số đoạn [ys[j], ys[j+1])
  99.  
  100.     vector<vector<Event>> ev(nx); // ev[ix] = danh sách event tại X chỉ số ix
  101.  
  102.     for (int i = 0; i < N; ++i) {
  103.         ll lx = xi[i];        // đã là xi[i] - W
  104.         ll rx = lx + W;       // thực ra = xi gốc
  105.         ll ly = yi[i];        // = yi gốc - H
  106.         ll ry = ly + H;       // = yi gốc
  107.  
  108.         ll w = wi[i];
  109.  
  110.         int ix1 = lower_bound(xs.begin(), xs.end(), lx) - xs.begin();
  111.         int ix2 = lower_bound(xs.begin(), xs.end(), rx + 1) - xs.begin(); // biên phải mở
  112.  
  113.         int iy1 = lower_bound(ys.begin(), ys.end(), ly) - ys.begin();
  114.         int iy2 = lower_bound(ys.begin(), ys.end(), ry + 1) - ys.begin() - 1; // đoạn [iy1, iy2]
  115.  
  116.         if (iy1 > iy2) continue; // đề cho H >= 1 nên thường không xảy ra
  117.  
  118.         ev[ix1].push_back({iy1, iy2, w});
  119.         if (ix2 < nx)
  120.             ev[ix2].push_back({iy1, iy2, -w});
  121.     }
  122.  
  123.     SegTree st(ny);
  124.     ll ans = 0;
  125.  
  126.     for (int ix = 0; ix < nx; ++ix) {
  127.         // xử lý tất cả sự kiện tại X này
  128.         for (const auto &e : ev[ix]) {
  129.             st.upd(e.y1, e.y2, e.v);
  130.         }
  131.         // sau khi cập nhật, max trên trục Y là đáp án nếu đặt X trong đoạn này
  132.         ans = max(ans, st.getMax());
  133.     }
  134.  
  135.     cout << ans << '\n';
  136.     return 0;
  137. }
  138.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5 3 2
0 2 7
1 0 5
1 3 5
2 1 3
3 1 9
stdout
copy 
17
https://ideone.com/zOQt2n
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!