Submission #971280

#	Time	Username	Problem	Language	Result	Execution time	Memory
971280		ind1v	Trading (IZhO13_trading)	C++11	100 / 100	202 ms	22700 KiB

trading

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;

int n, m;
multiset<int> mts;
int a[N];
vector<array<int, 3>> e;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int l, r, x;
    cin >> l >> r >> x;
    e.push_back(array<int, 3>{l, x - l, 0});
    e.push_back(array<int, 3>{r + 1, x - l, 1});
  }
  memset(a, -0x3f, sizeof(a));
  sort(e.begin(), e.end());
  for (int i = 1, j = 0; i <= n; i++) {
    while (j < (int) e.size() && e[j][0] <= i) {
      if (e[j][2] == 0) {
        mts.insert(e[j][1]);
      } else {
        mts.erase(mts.find(e[j][1]));
      }
      j++;
    }
    if (mts.empty()) {
      cout << 0 << ' ';
    } else {
      cout << *mts.rbegin() + i << ' ';
    }
  }
  return 0;
}

• Subtask 1: 100 / 100