제출 #90490

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90490		xiaowuc1	거래 (IZhO13_trading)	C++14	100 / 100	212 ms	10532 KiB

trading

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> matrix;

int lazy[1200000];
int sz = 300000;
void update(int idx, int l, int r, int lhs, int rhs, int v) {
  if(l >= lhs && r <= rhs) {
    lazy[idx] = max(lazy[idx], v);
    return;
  }
  lazy[2*idx] = max(lazy[2*idx], lazy[idx]);
  lazy[2*idx+1] = max(lazy[2*idx+1], lazy[idx]);
  int m = (l+r)/2;
  if(m >= lhs) update(2*idx, l, m, lhs, rhs, v);
  if(m+1 <= rhs) update(2*idx+1, m+1, r, lhs, rhs, v);
}
void update(int l, int r, int v) {
  update(1, 1, sz, l, r, v);
}
void solve(int idx, int l, int r, vector<int>& ret) {
  if(l == r) {
    ret.push_back(max(0, l + lazy[idx]));
    return;
  }
  lazy[2*idx] = max(lazy[2*idx], lazy[idx]);
  lazy[2*idx+1] = max(lazy[2*idx+1], lazy[idx]);
  int m = (l+r)/2;
  solve(2*idx, l, m, ret);
  solve(2*idx+1, m+1, r, ret);
}
void solve(vector<int>& ret) {
  solve(1, 1, sz, ret);
}

void solve() {
  int n, m;
  cin >> n >> m;
  for(int i = 1; i < 1200000; i++) lazy[i] = -1e9;
  while(m--) {
    int l, r, x;
    cin >> l >> r >> x;
    update(l, r, x-l);
  }
  vector<int> ret;
  ret.reserve(n);
  solve(ret);
  for(int i = 1; i <= n; i++) {
    cout << ret[i-1];
    if(i == n) cout << endl;
    else cout << " ";
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL);
  solve();
}

• Subtask 1: 100 / 100