oj.uz

Submission #83710

# Submission time Handle Problem Language Result Execution time Memory
83710 2018-11-10T04:39:43 Z mra2322001 Trading (IZhO13_trading) C++14
100 / 100
 287 ms 7112 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)

using namespace std;
typedef long long ll;
const int N = 300002;

int n, t[N*4];

void up(int k, int l, int r, int i, int j, int x){
    if(r < i || l > j) return ;
    if(l >= i && r <= j){
        t[k] = max(t[k], l - i + x);
        return ;
    }
    int m = (l + r)/2;
    up(k*2, l, m, i, j, x);
    up(k*2 + 1, m + 1, r, i, j, x);
}

int res= 0 ;
void get1(int k, int l, int r, int i){
    if(l==r){
        res = max(res, t[k]);
        return ;
    }
    if(t[k]) res = max(res, t[k] + i - l);
    int m = (l + r)/2;
    if(i <= m) get1(k*2, l, m, i);
    else get1(k*2 + 1, m + 1, r, i);
}

int main(){
    ios_base::sync_with_stdio(0);

    int q;
    cin >> n >> q;
    while(q--){
        int l, r, x; cin >> l >> r >> x;
        up(1, 1, n, l, r, x);
    }
    f1(i, n) {
        res = 0;
        get1(1, 1, n, i);
        cout << res << " ";
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 620 KB Output is correct
4 Correct 3 ms 628 KB Output is correct
5 Correct 3 ms 732 KB Output is correct
6 Correct 4 ms 732 KB Output is correct
7 Correct 163 ms 4936 KB Output is correct
8 Correct 162 ms 5588 KB Output is correct
9 Correct 181 ms 5588 KB Output is correct
10 Correct 164 ms 5588 KB Output is correct
11 Correct 274 ms 5860 KB Output is correct
12 Correct 197 ms 5860 KB Output is correct
13 Correct 216 ms 5860 KB Output is correct
14 Correct 205 ms 5860 KB Output is correct
15 Correct 225 ms 5860 KB Output is correct
16 Correct 248 ms 5860 KB Output is correct
17 Correct 226 ms 6420 KB Output is correct
18 Correct 277 ms 7096 KB Output is correct
19 Correct 236 ms 7096 KB Output is correct
20 Correct 287 ms 7112 KB Output is correct