oj.uz

Submission #725712

# Submission time Handle Problem Language Result Execution time Memory
725712 2023-04-17T23:46:42 Z Abrar_Al_Samit Wall (IOI14_wall) C++17
61 / 100
 391 ms 58352 KB 
#include <bits/stdc++.h>
using namespace std;
#include "wall.h"

const int INF = 1e9;
const int nax = 5e5 + 3;

pair<int, int>st[nax * 4];


void propagate(int v) {
    for(int c : {v*2, v*2+1}) {
        st[c].first = max(st[v].first, st[c].first);
        st[c].second = max(st[c].first, st[c].second);

        st[c].second = min(st[c].second, st[v].second);
        st[c].first = min(st[c].first, st[c].second);
    }
    st[v] = {-INF, INF};
}
void maximize(int l, int r, int L, int R, int val, int v) {
    if(l>R || r<L) return;
    if(l>=L && r<=R) {
        st[v].first = max(st[v].first, val);
        st[v].second = max(st[v].first, st[v].second);
        return;
    }
    propagate(v);
    int mid = (l+r)/2;
    maximize(l, mid, L, R, val, v*2);
    maximize(mid+1, r, L, R, val, v*2+1);
}
void minimize(int l, int r, int L, int R, int val, int v) {
    if(l>R || r<L) return;
    if(l>=L && r<=R) {
        st[v].second = min(st[v].second, val);
        st[v].first = min(st[v].first, st[v].second);
        return;
    }
    propagate(v);
    int mid = (l+r)/2;
    minimize(l, mid, L, R, val, v*2);
    minimize(mid+1, r, L, R, val, v*2+1);   
}
int query(int l, int r, int p, int v) {
    if(l==r) {
        return min(max(0, st[v].first), st[v].second);
    }
    propagate(v);
    int mid = (l+r)/2;
    if(p<=mid) return query(l, mid, p, v*2);
    else return query(mid+1, r, p, v*2+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i=1; i<nax * 4; ++i) {
        st[i] = {-INF, INF};
    }
    for(int i=0; i<k; ++i) {
        if(op[i]==1) {
            maximize(1, n, left[i]+1, right[i]+1, height[i], 1);
        } else {
            minimize(1, n, left[i]+1, right[i]+1, height[i], 1);
        }
    }
    for(int i=0; i<n; ++i) {
        finalHeight[i] = query(1, n, i+1, 1);
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 9 ms 16060 KB Output is correct
3 Correct 8 ms 15956 KB Output is correct
4 Correct 12 ms 16212 KB Output is correct
5 Correct 12 ms 16212 KB Output is correct
6 Correct 12 ms 16212 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 150 ms 25732 KB Output is correct
3 Correct 140 ms 21372 KB Output is correct
4 Correct 372 ms 28272 KB Output is correct
5 Correct 270 ms 30404 KB Output is correct
6 Correct 271 ms 29112 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15828 KB Output is correct
2 Correct 10 ms 15992 KB Output is correct
3 Correct 8 ms 15984 KB Output is correct
4 Correct 12 ms 16188 KB Output is correct
5 Correct 12 ms 16148 KB Output is correct
6 Correct 13 ms 16184 KB Output is correct
7 Correct 8 ms 15920 KB Output is correct
8 Correct 146 ms 25684 KB Output is correct
9 Correct 146 ms 21316 KB Output is correct
10 Correct 374 ms 26048 KB Output is correct
11 Correct 263 ms 31256 KB Output is correct
12 Correct 273 ms 31288 KB Output is correct
13 Correct 8 ms 15956 KB Output is correct
14 Correct 150 ms 29588 KB Output is correct
15 Correct 31 ms 17124 KB Output is correct
16 Correct 365 ms 34292 KB Output is correct
17 Correct 260 ms 33584 KB Output is correct
18 Correct 264 ms 33640 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15828 KB Output is correct
2 Correct 10 ms 15984 KB Output is correct
3 Correct 9 ms 15936 KB Output is correct
4 Correct 14 ms 16100 KB Output is correct
5 Correct 13 ms 16140 KB Output is correct
6 Correct 12 ms 16188 KB Output is correct
7 Correct 9 ms 15956 KB Output is correct
8 Correct 142 ms 25596 KB Output is correct
9 Correct 138 ms 21280 KB Output is correct
10 Correct 382 ms 26088 KB Output is correct
11 Correct 263 ms 31216 KB Output is correct
12 Correct 269 ms 31460 KB Output is correct
13 Correct 7 ms 15924 KB Output is correct
14 Correct 145 ms 29540 KB Output is correct
15 Correct 30 ms 17136 KB Output is correct
16 Correct 391 ms 34132 KB Output is correct
17 Correct 267 ms 33556 KB Output is correct
18 Correct 263 ms 33612 KB Output is correct
19 Runtime error 180 ms 58352 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -