oj.uz

Submission #1100798

# Submission time Handle Problem Language Result Execution time Memory
1100798 2024-10-14T18:25:40 Z Dan4Life Wall (IOI14_wall) C++17
100 / 100
 826 ms 67400 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int mxN = (int)2e6+10;
const int INF = (int)1e9;
 
int n, q, x[mxN];
array<int,2> seg[mxN*2], Init={INF,-INF};
 
void prop(int p, int l, int r){
    if(l==r or seg[p]==Init) return;
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    auto [a,b] = seg[p];
    seg[p+1][0] = min(a, max(seg[p+1][0], b));
    seg[p+1][1] = max(seg[p+1][1], b);
    seg[rp][0] = min(a, max(seg[rp][0], b));
    seg[rp][1] = max(seg[rp][1], b);
    seg[p] = Init;
}
 
void upd(int i, int j, int a, int b, int p=0, int l=0, int r=n-1){
    if(i>j or i>r or j<l) return;
    if(i<=l and r<=j){
        seg[p][0] = min(a, max(seg[p][0], b));
        seg[p][1] = max(seg[p][1], b);
        return;
    }
    prop(p,l,r);
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    upd(i,j,a,b,p+1,l,mid); upd(i,j,a,b,rp,mid+1,r);
}
 
int query(int i, int p=0, int l=0, int r=n-1){
    if(l==r) return min(seg[p][0],max(x[l],seg[p][1]));
    prop(p,l,r);
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    if(i<=mid) return query(i,p+1,l,mid);
    return query(i,rp,mid+1,r);
}
 
void buildWall(int N, int k, int o[], int l[], int r[], int h[], int ans[]){
    n = N; fill(seg,seg+2*n,Init);
    for(int i = 0; i < k; i++){
        int a, b;
        if(o[i]==1) a = INF, b = h[i];
        else a = h[i], b = -INF;
        upd(l[i],r[i],a,b);
    }
    for(int i = 0; i < n; i++) ans[i] = query(i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 5 ms 592 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 5 ms 712 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 90 ms 9772 KB Output is correct
3 Correct 139 ms 5960 KB Output is correct
4 Correct 436 ms 10888 KB Output is correct
5 Correct 253 ms 11592 KB Output is correct
6 Correct 241 ms 16136 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 5 ms 592 KB Output is correct
5 Correct 5 ms 720 KB Output is correct
6 Correct 5 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 101 ms 8116 KB Output is correct
9 Correct 177 ms 7500 KB Output is correct
10 Correct 448 ms 13636 KB Output is correct
11 Correct 259 ms 19528 KB Output is correct
12 Correct 231 ms 11600 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 93 ms 8264 KB Output is correct
15 Correct 29 ms 3664 KB Output is correct
16 Correct 433 ms 15440 KB Output is correct
17 Correct 244 ms 16200 KB Output is correct
18 Correct 240 ms 18504 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 6 ms 848 KB Output is correct
5 Correct 5 ms 592 KB Output is correct
6 Correct 5 ms 716 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 93 ms 11592 KB Output is correct
9 Correct 149 ms 7748 KB Output is correct
10 Correct 425 ms 11016 KB Output is correct
11 Correct 255 ms 11544 KB Output is correct
12 Correct 229 ms 18512 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 86 ms 8216 KB Output is correct
15 Correct 25 ms 3176 KB Output is correct
16 Correct 413 ms 16292 KB Output is correct
17 Correct 239 ms 16200 KB Output is correct
18 Correct 238 ms 11156 KB Output is correct
19 Correct 779 ms 59208 KB Output is correct
20 Correct 825 ms 62124 KB Output is correct
21 Correct 818 ms 67400 KB Output is correct
22 Correct 811 ms 56904 KB Output is correct
23 Correct 775 ms 62280 KB Output is correct
24 Correct 801 ms 56904 KB Output is correct
25 Correct 788 ms 62356 KB Output is correct
26 Correct 816 ms 67400 KB Output is correct
27 Correct 823 ms 59204 KB Output is correct
28 Correct 793 ms 56904 KB Output is correct
29 Correct 799 ms 56904 KB Output is correct
30 Correct 826 ms 56904 KB Output is correct