oj.uz

Submission #1100797

# Submission time Handle Problem Language Result Execution time Memory
1100797 2024-10-14T18:25:16 Z Dan4Life Wall (IOI14_wall) C++17
100 / 100
 946 ms 69860 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; prop(p,l,r);
    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;
    }
    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);
}

Compilation message

wall.cpp: In function 'void upd(int, int, int, int, int, int, int)':
wall.cpp:22:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   22 |     if(i>j or i>r or j<l) return; prop(p,l,r);
      |     ^~
wall.cpp:22:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   22 |     if(i>j or i>r or j<l) return; prop(p,l,r);
      |                                   ^~~~

Subtask #1
8.0 / 8.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 2 ms 480 KB Output is correct
4 Correct 6 ms 592 KB Output is correct
5 Correct 5 ms 848 KB Output is correct
6 Correct 5 ms 592 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 85 ms 8164 KB Output is correct
3 Correct 161 ms 5960 KB Output is correct
4 Correct 472 ms 11080 KB Output is correct
5 Correct 261 ms 21572 KB Output is correct
6 Correct 251 ms 20044 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 2 ms 336 KB Output is correct
4 Correct 6 ms 592 KB Output is correct
5 Correct 6 ms 848 KB Output is correct
6 Correct 5 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 86 ms 8092 KB Output is correct
9 Correct 166 ms 8032 KB Output is correct
10 Correct 473 ms 16132 KB Output is correct
11 Correct 263 ms 21648 KB Output is correct
12 Correct 243 ms 20044 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 91 ms 13876 KB Output is correct
15 Correct 27 ms 3680 KB Output is correct
16 Correct 468 ms 20812 KB Output is correct
17 Correct 258 ms 20300 KB Output is correct
18 Correct 245 ms 20300 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 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 6 ms 592 KB Output is correct
5 Correct 5 ms 848 KB Output is correct
6 Correct 5 ms 592 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 92 ms 11228 KB Output is correct
9 Correct 159 ms 8028 KB Output is correct
10 Correct 453 ms 11048 KB Output is correct
11 Correct 270 ms 21580 KB Output is correct
12 Correct 250 ms 20044 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 94 ms 14072 KB Output is correct
15 Correct 29 ms 3668 KB Output is correct
16 Correct 492 ms 20812 KB Output is correct
17 Correct 249 ms 20208 KB Output is correct
18 Correct 251 ms 20312 KB Output is correct
19 Correct 888 ms 69860 KB Output is correct
20 Correct 905 ms 67148 KB Output is correct
21 Correct 892 ms 69804 KB Output is correct
22 Correct 837 ms 67216 KB Output is correct
23 Correct 878 ms 65612 KB Output is correct
24 Correct 919 ms 67148 KB Output is correct
25 Correct 900 ms 67328 KB Output is correct
26 Correct 905 ms 69712 KB Output is correct
27 Correct 929 ms 69856 KB Output is correct
28 Correct 887 ms 67260 KB Output is correct
29 Correct 884 ms 67240 KB Output is correct
30 Correct 946 ms 67148 KB Output is correct