oj.uz

Submission #83709

# Submission time Handle Problem Language Result Execution time Memory
83709 2018-11-10T04:38:09 Z mra2322001 Trading (IZhO13_trading) C++14
0 / 100
 331 ms 66560 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], pos[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);
        pos[k] = 1;
        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(pos[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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 3 ms 752 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 4 ms 948 KB Output is correct
7 Correct 146 ms 7156 KB Output is correct
8 Correct 220 ms 11796 KB Output is correct
9 Correct 169 ms 14164 KB Output is correct
10 Correct 164 ms 16088 KB Output is correct
11 Correct 205 ms 22524 KB Output is correct
12 Correct 199 ms 25236 KB Output is correct
13 Correct 237 ms 30432 KB Output is correct
14 Correct 224 ms 33528 KB Output is correct
15 Correct 273 ms 38880 KB Output is correct
16 Correct 253 ms 43668 KB Output is correct
17 Correct 249 ms 50864 KB Output is correct
18 Correct 304 ms 57164 KB Output is correct
19 Correct 268 ms 60956 KB Output is correct
20 Runtime error 331 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.