oj.uz

답안 #985914

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
985914 2024-05-19T10:07:15 Z LOLOLO 거래 (IZhO13_trading) C++17
100 / 100
 290 ms 33876 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 3e5 + 10;

int seg[N * 4], laz[N * 4];

void push(int id) {
    int &t = laz[id];
    laz[id * 2] += t;
    laz[id * 2 + 1] += t;
    seg[id * 2] += t;
    seg[id * 2 + 1] += t;
    t = 0;
}

void upd(int id, int l, int r, int u, int v, int c) {
    if (l > v || r < u)
        return;

    if (l >= u && r <= v) {
        laz[id] += c;
        seg[id] += c;
        return;
    }

    push(id);
    int m = (l + r) / 2;
    upd(id * 2, l, m, u, v, c);
    upd(id * 2 + 1, m + 1, r, u, v, c);
    seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
}

void run(int id, int l, int r, int p, int v) {
    if (l > p || r < p)
        return;

    if (l == r) {
        seg[id] = v;
        laz[id] = 0;
        return;
    } 

    push(id);
    int m = (l + r) / 2;
    run(id * 2, l, m, p, v);
    run(id * 2 + 1, m + 1, r, p, v);
    seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
}

vector <int> event[N];
int l[N], r[N], v[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    seg[1] = laz[1] = -1e8;
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        cin >> l[i] >> r[i] >> v[i];
        event[l[i]].pb(i);
        event[r[i] + 1].pb(-i);
    }

    for (int i = 1; i <= n; i++) {
        upd(1, 1, m, 1, m, 1);
        for (auto x : event[i]) {
            if (x > 0) {
                run(1, 1, m, x, v[x]);
            } else {
                run(1, 1, m, -x, -1e8);
            }
        }

        cout << max(0, seg[1]) << " ";
    }

    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8796 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 4 ms 8796 KB Output is correct
4 Correct 4 ms 8796 KB Output is correct
5 Correct 4 ms 8796 KB Output is correct
6 Correct 7 ms 8796 KB Output is correct
7 Correct 117 ms 21032 KB Output is correct
8 Correct 132 ms 23176 KB Output is correct
9 Correct 181 ms 22640 KB Output is correct
10 Correct 146 ms 21828 KB Output is correct
11 Correct 157 ms 25164 KB Output is correct
12 Correct 203 ms 24340 KB Output is correct
13 Correct 209 ms 25300 KB Output is correct
14 Correct 176 ms 24244 KB Output is correct
15 Correct 217 ms 26988 KB Output is correct
16 Correct 209 ms 26392 KB Output is correct
17 Correct 263 ms 26432 KB Output is correct
18 Correct 232 ms 32244 KB Output is correct
19 Correct 211 ms 26564 KB Output is correct
20 Correct 290 ms 33876 KB Output is correct