Submission #1037077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037077		vjudge1	Trading (IZhO13_trading)	C++17	100 / 100	245 ms	7496 KiB

trading

#include<bits/stdc++.h>

using namespace std;

#define bug(...)                        __f (#__VA_ARGS__, __VA_ARGS__)

#define F                               first
#define S                               second
#define pb                              push_back
#define vi                              vector <int>
#define pii                             pair <int, int>
#define vpi                             vector <pii>
#define vpp                             vector <pair <int, pii>>
#define mii                             map <int, int>
#define mpi                             map <pii, int>
#define spi                             set <pii>
#define endl                            "\n"
#define sz(x)                           ((int) x.size())
#define all(p)                          p.begin(), p.end()
#define double                          long double
#define que_max                         priority_queue <int>
#define que_min                         priority_queue <int, vi, greater<int>>
#define print(a)                        for (auto x: a) cout << x << " "; cout << endl
#define print1(a)                       for (auto x: a) cout << x.F << " " << x.S << endl
#define print2(a, l, r)                 for (int i = l; i < r; ++ i) cout << a[i] << " "; cout << endl

#define GET(n, id)                      (!!(n & (1LL << id))) // lay bit thu id
#define ON(n, id)                       (n | (1LL << id)) // bit thu id luon la 1
#define OFF(n, id)                      (n & ~(1LL << id)) // bit thu id luon la 0
#define BIT0(n, id)                     (n & (-1LL << (id + 1))) // chinh tat ca id bit dau thanh 0 (id >= 1)
#define BIT0IJ(n, i, j)                 (n & ((-1LL << (j + 1)) | ((1LL << i) - 1))) // chinh tat ca bit tu i den j thanh 0 (id = 0, 1, ...)
#define REPLACE_BIT(n, i, j, m)         (BIT0IJ(n, i, j) | (m << i))

#define MSB(mask)                       63 - __builtin_clzll(mask) // so bit 0 o cuoi
#define LSB(mask)                       __builtin_ctzll(mask) // so bit 0 o dau
#define ONE(mask)                       __builtin_popcountll(mask) // so bit bat
#define mem(a, b)                       memset(a, b, sizeof(a));
#define el                              cout << "\n";

#define fu(i, l, r)                    for (int i = l; i <= r; ++ i)
#define fd(i, l, r)                    for (int i = r; i >= l; --i)

template <typename Arg1>void __f (const char* name, Arg1 && arg1) {cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* name, Arg1 && arg1, Args && ... args)
{
    const char* comma = strchr (name + 1, ',');
    cout.write (name, comma - name) << " : " << arg1 << " | "; __f (comma + 1, args ...);
}

const int N = 300005;

struct node {
    int lazy, val;
};

node nodes[4 * N];

void down(int id, int l, int r) {
    if (!nodes[id].lazy) return;

    nodes[id].val = max(nodes[id].val, nodes[id].lazy);

    if (l != r){
        int mid = (l + r) / 2;
        nodes[id*2].lazy = max(nodes[id].lazy, nodes[id*2].lazy);
        nodes[id*2+1].lazy = max(nodes[id*2 + 1].lazy, nodes[id].lazy + mid + 1 - l);
    }
    nodes[id].lazy = 0;
}

void update(int id, int l, int r, int u, int v, int val) {
    down(id, l, r);
    if (v < l or u > r) return;
    if (u <= l and r <= v) {
        nodes[id].lazy = max(nodes[id].lazy, val + l - u);
        return;
    }
    int mid = (l + r) / 2;
    down(id, l, r);
    update(id * 2, l, mid, u, v, val);
    update(id * 2 + 1, mid + 1, r, u, v, val);
    nodes[id].val = max(nodes[id * 2].val, nodes[id * 2 + 1].val);
}

int get(int id, int l, int r, int u, int v) {
    down(id, l, r);
    if (v < l or u > r) return 0;
    if (l == r) return nodes[id].val;
    int mid = (l + r) / 2;
    return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}

int n, m;
void solve (){
    cin >> n >> m;
    fu (i, 1, m){
        int l, r, x; cin >> l >> r >> x;
        update(1, 1, n, l, r, x);
    }

    fu (i, 1, n) cout << get(1, 1, n, i, i) << " ";
}



signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t --) solve();
    return 0;
}

• Subtask 1: 100 / 100