Submission #1191110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191110		lopkus	Trading (IZhO13_trading)	C++20	100 / 100	128 ms	34704 KiB

trading

#include <bits/stdc++.h>

#define int int64_t

const int N = 500001;

const int64_t inf = 1e15;

struct segtree{
    int64_t t[4*N];
    int64_t query(int v, int tl, int tr, int l, int r) {
        if(tl > r || tr < l) {
            return -inf;
        }
        if(tl >= l && tr <= r) {
            return t[v];
        }
        int tm = (tl + tr) / 2;
        return std::max(query(v * 2, tl, tm, l, r), query(v * 2 + 1, tm + 1, tr, l, r));
    }
    void update(int v, int tl, int tr, int index, int64_t value) {
        if(tl == tr) {
            t[v] = std::max(t[v], value);
        }
        else {
            int tm = (tl + tr) / 2;
            if(index <= tm) {
                update(v * 2, tl, tm, index, value);
            }
            else {
                update(v * 2 + 1, tm + 1, tr, index, value);
            }
            t[v] = std::max(t[v * 2], t[v * 2 + 1]);
        }
    }
}seg;

void solve() {
  int n, m;
  std::cin >> n >> m;
  for(int i = 1; i <= 4 * n; i++) {
    seg.t[i] = -inf;
  }
  std::vector<int> l(m + 1), r(m + 1), x(m + 1);
  std::vector<std::pair<int,int64_t>> upd[n + 1];
  for(int i = 1; i <= m; i++) {
    std::cin >> l[i] >> r[i] >> x[i];
    upd[l[i]].push_back({r[i], x[i] - l[i]});
  }
  std::vector<int64_t> ans(n + 1, 0);
  for(int i = 1; i <= n; i++) {
    for(auto [R, val] : upd[i]) {
      seg.update(1, 1, n, R, val);
    }
    ans[i] = std::max(ans[i], i + seg.query(1, 1, n, i, n));
  }
  for(int i = 1; i <= n; i++) {
    std::cout << ans[i] << " ";
  }
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t = 1;
  //std::cin >> t;
  while (t--) {
      solve();
  }

  return 0;
}

• Subtask 1: 100 / 100