oj.uz

답안 #380264

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
380264 2021-03-20T18:29:17 Z Aryan_Raina 거래 (IZhO13_trading) C++14
100 / 100
 279 ms 10604 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define ar array

const int INF = 1e17;
const int MOD = 1e9;

struct SegTree {
    vector<int> values;
    int size;
    void init(int n) {
        size = 1;
        while (size < n) size <<= 1;
        values.resize(2*size);
    }
    void modify(int l, int r, int v, int x, int lx, int rx) {
        if (l >= rx || lx >= r) return;
        if (l <= lx && rx <= r) {
            values[x] = max(values[x], v + (lx - l));
            //cout<<lx<<" "<<rx<<" "<<values[x]<<endl;
            return;
        }
        int m = (lx + rx) >> 1;
        modify(l, r, v, 2*x + 1, lx, m);
        modify(l, r, v, 2*x + 2, m, rx);
    }
    void modify(int l, int r, int v) {
        modify(l, r, v, 0, 0, size);
    }
    int get(int i, int x, int lx, int rx) { 
        if (rx - lx == 1) return values[x];
        int m = (lx + rx) >> 1;
        int ans = 0;
        if (i < m) {
            ans = get(i, 2*x+1, lx, m);
        } else {
            ans = get(i, 2*x+2, m, rx);
        }
        if (values[x]) ans = max(ans, values[x] + i-lx);
        return ans;
    }
    int get(int i) {
        return get(i, 0, 0, size);
    }
};

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin>>n>>m;
    SegTree st; st.init(n);
    for (int i = 0; i < m; i++) {
        int l, r, v; cin>>l>>r>>v; --l, --r;
        st.modify(l, r+1, v);
    }
    for (int i = 0; i < n; i++) cout<<st.get(i)<<" ";
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 133 ms 5484 KB Output is correct
8 Correct 147 ms 5868 KB Output is correct
9 Correct 154 ms 5748 KB Output is correct
10 Correct 162 ms 5484 KB Output is correct
11 Correct 175 ms 6124 KB Output is correct
12 Correct 183 ms 5740 KB Output is correct
13 Correct 201 ms 5996 KB Output is correct
14 Correct 200 ms 5868 KB Output is correct
15 Correct 217 ms 5996 KB Output is correct
16 Correct 222 ms 5996 KB Output is correct
17 Correct 226 ms 10220 KB Output is correct
18 Correct 246 ms 10476 KB Output is correct
19 Correct 265 ms 10220 KB Output is correct
20 Correct 279 ms 10604 KB Output is correct