Submission #321992

#	Time	Username	Problem	Language	Result	Execution time	Memory
321992		jovan_b	Trading (IZhO13_trading)	C++17	0 / 100	1 ms	364 KiB

trading

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

int seg[1200005];

void propagate(int node, int l, int r){
    if(l == r) return;
    seg[node*2] = max(seg[node*2], seg[node]);
    seg[node*2+1] = max(seg[node*2+1], seg[node]);
}

void upd(int node, int l, int r, int tl, int tr, int val){
    propagate(node, l, r);
    if(tl > r || l > tr) return;
    if(tl <= l && r <= tr){
        seg[node] = max(seg[node], val);
        propagate(node, l, r);
        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;
    }
    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: 0 / 100