Submission #89387

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
89387	2018-12-13T07:04:45 Z	turbat	Trading (IZhO13_trading)	C++14	100 / 100	503 ms	40632 KB

trading

#include <bits/stdc++.h>
using namespace std;
#define N 300005
int n, m, l, r, x, seg[4 * N], ans[N];
void update(int node, int L, int R, int l, int r){
    if (L > r || l > R) return;
    if (l <= L && r >= R){
        seg[node] = max(seg[node], x);
        return;
    }
    int mid = (L + R)/2;
    update(node * 2, L, mid, l, r);
    update(node * 2 + 1, mid + 1, R, l, r);
}
void res(int node, int l, int r){
    if (l == r){
        ans[l] = seg[node];
        return;
    }
    int mid = (l + r)/2;
    seg[node * 2] = max(seg[node], seg[node * 2]);
    res(node * 2, l, mid);
    seg[node * 2 + 1] = max(seg[node], seg[node * 2 + 1]);
    res(node * 2 + 1, mid + 1, r);
}
int main (){
    cin >> n>> m;
    for (int i = 0;i < 4 * n;i++) seg[i] = -1e9;
    while (m--){
        cin >> l>> r>> x;
        x -= (l - 1);
        update(1, 1, n, l, r);
    }
    res(1, 1, n);
    for (int i = 0;i < n;i++)
        cout << max(ans[i + 1] + i, 0)<<" ";
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	464 KB	Output is correct
4	Correct	3 ms	640 KB	Output is correct
5	Correct	4 ms	704 KB	Output is correct
6	Correct	6 ms	760 KB	Output is correct
7	Correct	234 ms	7352 KB	Output is correct
8	Correct	266 ms	11136 KB	Output is correct
9	Correct	271 ms	11308 KB	Output is correct
10	Correct	286 ms	11308 KB	Output is correct
11	Correct	299 ms	12444 KB	Output is correct
12	Correct	341 ms	12444 KB	Output is correct
13	Correct	349 ms	12692 KB	Output is correct
14	Correct	347 ms	12692 KB	Output is correct
15	Correct	395 ms	13084 KB	Output is correct
16	Correct	424 ms	18216 KB	Output is correct
17	Correct	396 ms	23528 KB	Output is correct
18	Correct	438 ms	28876 KB	Output is correct
19	Correct	413 ms	34116 KB	Output is correct
20	Correct	503 ms	40632 KB	Output is correct