Submission #47546

#TimeUsernameProblemLanguageResultExecution timeMemory
47546tieunhiTrading (IZhO13_trading)C++14
0 / 100
5 ms3996 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define mp make_pair #define F first #define S second #define PB push_back #define mid (r + l)/2 #define N 100005 #define maxc 1000000007 using namespace std; int n, m; struct IntervalTree { int t[N << 2]; void build() { for (int i = 0; i < (N << 2); i++) t[i] = -maxc; } void update(int l, int r, int id, int x, int y, int val) { if (l > y || r < x) return; if (l >= x && r <= y) { t[id] = max(t[id], val); return; } update(l, mid, id*2, x, y, val); update(mid+1, r, id*2+1, x, y, val); } int get(int l, int r, int id, int x) { if (l > x || r < x) return -maxc; if (l == r) return t[id]; int z = t[id]; int a = get(l, mid, id*2, x); int b = get(mid+1, r, id*2+1, x); return max({z, a, b}); } }t; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("INP.TXT", "r", stdin); cin >> n >> m; t.build(); for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; w -= (u-1); t.update(1, n, 1, u, v, w); } for (int i = 1; i <= n; i++) { int res = t.get(1, n, 1, i); if (res == -maxc) cout <<0<<" "; else cout <<t.get(1, n, 1, i) + i - 1<<" "; } }
#Verdict Execution timeMemoryGrader output
Fetching results...