oj.uz

Submission #1113656

# Submission time Handle Problem Language Result Execution time Memory
1113656 2024-11-17T00:44:17 Z sunboi Wall (IOI14_wall) C++17
61 / 100
 507 ms 64368 KB 
#include <bits/stdc++.h>
using namespace std;


const int N = 2e5 + 1000;
vector<int> a(N);
vector<pair<long long, long long>> t(4 * N);
vector<int>lazy(4 * N);

void push(int v, int vl, int vr){
    if (vr == vl) return;
    
    t[2 * v].first = min(max(t[2 * v].first, t[v].first), t[v].second);
    
    t[2 * v ].second = max(min(t[2 * v].second, t[v].second), t[v].first);
 
    t[2 * v + 1].first = min(max(t[2 * v + 1].first, t[v].first), t[v].second);
    
    t[2 * v + 1].second = max(min(t[2 * v + 1].second, t[v].second), t[v].first);
    
    t[v] = {0, 1e9};
}




void update(int v, int vl, int vr, int l, int r, long long x, int tt){
    if (vl > r || vr < l) return;
    
    push(v, vl ,vr);
    if (vl >= l && vr <= r){
        if (tt == 1){
            t[v] = {max(t[v].first, x), max(t[v].second, x)};
        }else{
            t[v] = {min(t[v].first, x), min(t[v].second, x)};
        }
        push(v, vl ,vr);
        
        return;
    }
    
    int vm = (vl + vr) / 2;
    
    update(2 * v, vl, vm, l, r, x, tt);
    update(2 * v + 1, vm + 1, vr, l, r, x, tt);

}


int get(int v, int vl, int vr, int x){
    if (vl > x || vr < x) return 0;
    push(v, vl ,vr);
    if (vr <= x && x <= vl){
        return t[v].first;
    }
    
    
    int vm = (vl + vr) / 2;
    
    return max(get(2 * v, vl, vm, x), get(2 * v + 1, vm + 1, vr, x));
    
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

    for (int i = 0; i < n; i++){
        a[i] = 0;
    }
    //build(1, 0, n - 1);
    for (int i = 0; i < k; i++){
        if (op[i] == 1){
            update(1, 0, n - 1, left[i], right[i], height[i], 1);
        }else update(1, 0, n - 1, left[i], right[i], height[i], 2);
        
    }
    for (int i = 0; i < n; i++){
        
        finalHeight[i] = get(1, 0, n - 1, i);
    }

    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16720 KB Output is correct
2 Correct 5 ms 16976 KB Output is correct
3 Correct 5 ms 16976 KB Output is correct
4 Correct 9 ms 16976 KB Output is correct
5 Correct 10 ms 17184 KB Output is correct
6 Correct 8 ms 16976 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16720 KB Output is correct
2 Correct 99 ms 24648 KB Output is correct
3 Correct 169 ms 20296 KB Output is correct
4 Correct 412 ms 25168 KB Output is correct
5 Correct 221 ms 35888 KB Output is correct
6 Correct 206 ms 34412 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16720 KB Output is correct
2 Correct 5 ms 16864 KB Output is correct
3 Correct 5 ms 16988 KB Output is correct
4 Correct 9 ms 17400 KB Output is correct
5 Correct 8 ms 16988 KB Output is correct
6 Correct 8 ms 16988 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 97 ms 30500 KB Output is correct
9 Correct 153 ms 23880 KB Output is correct
10 Correct 393 ms 34896 KB Output is correct
11 Correct 220 ms 35912 KB Output is correct
12 Correct 207 ms 34384 KB Output is correct
13 Correct 4 ms 16720 KB Output is correct
14 Correct 107 ms 30512 KB Output is correct
15 Correct 35 ms 18000 KB Output is correct
16 Correct 507 ms 35144 KB Output is correct
17 Correct 244 ms 34632 KB Output is correct
18 Correct 228 ms 34632 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16720 KB Output is correct
2 Correct 5 ms 16976 KB Output is correct
3 Correct 5 ms 16976 KB Output is correct
4 Correct 9 ms 16976 KB Output is correct
5 Correct 9 ms 16976 KB Output is correct
6 Correct 9 ms 16976 KB Output is correct
7 Correct 4 ms 16720 KB Output is correct
8 Correct 100 ms 30428 KB Output is correct
9 Correct 159 ms 23892 KB Output is correct
10 Correct 408 ms 34972 KB Output is correct
11 Correct 246 ms 35912 KB Output is correct
12 Correct 222 ms 33028 KB Output is correct
13 Correct 4 ms 16720 KB Output is correct
14 Correct 105 ms 30348 KB Output is correct
15 Correct 30 ms 18000 KB Output is correct
16 Correct 493 ms 31660 KB Output is correct
17 Correct 214 ms 34448 KB Output is correct
18 Correct 226 ms 34632 KB Output is correct
19 Runtime error 146 ms 64368 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -