Submission #90770

#	Time	Username	Problem	Language	Result	Execution time	Memory
90770		inom	Trading (IZhO13_trading)	C++14	0 / 100	18 ms	19320 KiB

trading

#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>

#define fi first
#define se second
#define new new228
#define pb push_back
#define rank rank228
#define int long long
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define in freopen("trading.in", "r", stdin)
#define out freopen("trading.out", "w", stdout)
 
using namespace std;
using namespace __gnu_pbds;
 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
 
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // st.oreder_of_key();

const int N = 300300;
const int MAXN = 4 * N;
const int INF = 1e15 + 7;
const int MOD = 998244353;
 
struct trader {
    int l, r, x, b;
};

int TN = 1;

int n, m;
int t[MAXN];
int d[MAXN];
trader a[N];

bool cmp(trader x, trader y) {
    if (x.b < y.b) {
        return true;
    }
    if (x.b > y.b) {
        return false;
    }
    else {
        if (x.l < y.l) {
            return true;
        }
        if (x.l > y.l) {
            return false;
        }
        else {
            if (x.r < y.r) {
                return true;
            }
            if (x.r > y.r) {
                return false;
            }
        }
    }
    return false;
}

void push(int v) {
    if (d[v] != 0) {
        t[v << 1] = t[v << 1 | 1] = d[v];
        d[v << 1] = d[v << 1 | 1] = d[v];
        d[v] = 0; return;
    }
}

void update(int v, int tl, int tr, int l, int r, int val) {
    if (tl > r || tr < l || l > r) {
        return;
    }
    if (tl == l && tr == r) {
        if (t[v] < val) {
            t[v] = val; d[v] = val;
            return;
        }
    }
    push(v);
    int tm = (tl + tr) >> 1;
    update(v << 1, tl, tm, l, min(tm, r), val);
    update(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r, val);
}

int get(int v, int tl, int tr, int pos) {
    if (tl == tr) {
        if (d[v] != 0) {
            t[v] = d[v];
        }
        return t[v];
    }
    push(v);
    int tm = (tl + tr) >> 1;
    if (pos <= tm) {
        return get(v << 1, tl, tm, pos);
    } else {
        return get(v << 1 | 1, tm + 1, tr, pos);
    }
}

void solve() {
    // scanf("%d %d", &n, &m);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        // scanf("%d %d %d", &a[i].l, a[i].r, a[i].x);
        cin >> a[i].l >> a[i].r >> a[i].x;
        a[i].b = a[i].x - a[i].l;
    }
    sort(a + 1, a + 1 + m, cmp);
    /*for (int i = 1; i <= m; i++) {
        cout << a[i].b << " " << a[i].l << " " << a[i].r << " " << a[i].x << "\n";
        // printf("%d %d %d %d\n", a[i].b, a[i].l, a[i].r, a[i].x);
    }*/
    fill(t, t + MAXN, -INF);
    for (int i = 1; i <= m; i++) {
        update(1, 1, n, a[i].l, a[i].r, a[i].b);
    }
    for (int i = 1; i <= n; i++) {
        int ans = get(1, 1, n, i);
        if (ans == -INF) {
            cout << 0 << " ";
        } else {
            cout << ans + i << " ";
        }
    }
    return;
}

signed main() {
    // in; out; // cin >> TN;
    while (TN--) { solve(); }
    return 0;
}

• Subtask 1: 0 / 100