Submission #1092144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092144		juicy	Trading (IZhO13_trading)	C++17	100 / 100	145 ms	12624 KiB

trading

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 3e5 + 5;

int n, m;
int s[4 * N];

void upd(int u, int v, int x, int id = 1, int l = 1, int r = n) {
  if (u <= l && r <= v) {
    s[id] = max(s[id], x);
    return;
  }
  int m = (l + r) / 2;
  if (u <= m) {
    upd(u, v, x, id * 2, l, m);
  }
  if (m < v) {
    upd(u, v, x, id * 2 + 1, m + 1, r);
  }
}

int qry(int i, int id = 1, int l = 1, int r = n) {
  if (l == r) {
    return s[id];
  }
  int m = (l + r) / 2;
  return max(s[id], i <= m ? qry(i, id * 2, l, m) : qry(i, id * 2 + 1, m + 1, r));
}

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

  cin >> n >> m;
  memset(s, -0x3f, sizeof(s));
  while (m--) {
    int l, r, x; cin >> l >> r >> x;
    upd(l, r, x - l);
  }
  for (int i = 1; i <= n; ++i) {
    cout << max(qry(i) + i, 0) << " ";
  }
  return 0;
}

• Subtask 1: 100 / 100