oj.uz

Submission #443794

# Submission time Handle Problem Language Result Execution time Memory
443794 2021-07-12T06:23:26 Z JovanB Trading (IZhO13_trading) C++17
100 / 100
 232 ms 12100 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
int seg[2000005];
 
void upd(int node, int l, int r, int tl, int tr, int val){
    if(tl > r || l > tr) return;
    if(tl <= l && r <= tr){
        seg[node] = max(seg[node], val);
        return;
    }
    int mid = (l+r)/2;
    upd(node*2, l, mid, tl, tr, val);
    upd(node*2+1, mid+1, r, tl, tr, val);
}
 
void ispisi(int node, int l, int r){
    if(l == r){
        cout << seg[node]+l << " ";
        return;
    }
    seg[node*2] = max(seg[node*2], seg[node]);
    seg[node*2+1] = max(seg[node*2+1], seg[node]);
    int mid = (l+r)/2;
    ispisi(node*2, l, mid);
    ispisi(node*2+1, mid+1, r);
}
 
void init(int node, int l, int r){
    if(l == r){
        seg[node] = -l;
        return;
    }
    seg[node] = -1000000000;
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
}
 
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;
 
    int n, m;
    cin >> n >> m;
    init(1, 1, n);
    for(int i=1; i<=m; i++){
        int l, r, x;
        cin >> l >> r >> x;
        upd(1, 1, n, l, r, x-l);
    }
    ispisi(1, 1, n);
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 111 ms 6064 KB Output is correct
8 Correct 127 ms 6576 KB Output is correct
9 Correct 133 ms 6696 KB Output is correct
10 Correct 139 ms 6724 KB Output is correct
11 Correct 142 ms 7468 KB Output is correct
12 Correct 154 ms 7600 KB Output is correct
13 Correct 163 ms 7836 KB Output is correct
14 Correct 166 ms 7748 KB Output is correct
15 Correct 185 ms 8484 KB Output is correct
16 Correct 196 ms 8496 KB Output is correct
17 Correct 190 ms 10736 KB Output is correct
18 Correct 203 ms 11228 KB Output is correct
19 Correct 200 ms 10808 KB Output is correct
20 Correct 232 ms 12100 KB Output is correct