oj.uz

Submission #81815

# Submission time Handle Problem Language Result Execution time Memory
81815 2018-10-27T01:45:53 Z mra2322001 Trading (IZhO13_trading) C++14
100 / 100
 383 ms 6844 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, m, t[4*N];

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

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

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

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 376 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 3 ms 572 KB Output is correct
6 Correct 4 ms 612 KB Output is correct
7 Correct 183 ms 3864 KB Output is correct
8 Correct 206 ms 4232 KB Output is correct
9 Correct 203 ms 4232 KB Output is correct
10 Correct 221 ms 4232 KB Output is correct
11 Correct 238 ms 4472 KB Output is correct
12 Correct 257 ms 4472 KB Output is correct
13 Correct 257 ms 4472 KB Output is correct
14 Correct 260 ms 4472 KB Output is correct
15 Correct 294 ms 4472 KB Output is correct
16 Correct 322 ms 4472 KB Output is correct
17 Correct 287 ms 6544 KB Output is correct
18 Correct 362 ms 6740 KB Output is correct
19 Correct 340 ms 6740 KB Output is correct
20 Correct 383 ms 6844 KB Output is correct