oj.uz

Submission #758412

# Submission time Handle Problem Language Result Execution time Memory
758412 2023-06-14T15:16:39 Z Dan4Life Wall (IOI14_wall) C++17
100 / 100
 1004 ms 75864 KB 
#include <bits/stdc++.h>
using namespace std;
const int mxN = (int)2e6+10;
int n, k, a[mxN];
array<int,2> seg[mxN*2],Init{0,mxN};
//maximize then minimize
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);
    for(int i : {0,1}){
        seg[p+1][i] = min(max(seg[p+1][i],seg[p][0]),seg[p][1]);
        seg[rp][i] = min(max(seg[rp][i],seg[p][0]),seg[p][1]);
    }
    seg[p]=Init;
}

void upd(int i, int j, int lv, int rv, int p=0, int l=0, int r=n-1){
    if(i>r or j<l or i>j) return; prop(p,l,r);
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    if(i<=l and r<=j){ 
        for(int k : {0,1}) 
          seg[p][k] = min(max(seg[p][k],lv),rv);
        return; 
    }
    upd(i,j,lv,rv,p+1,l,mid), upd(i,j,lv,rv,rp,mid+1,r);
}

void query(int p=0, int l=0, int r=n-1){
    if(l==r){ a[l]=min(seg[p][0],seg[p][1]); return; } prop(p,l,r);
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    query(p+1,l,mid), query(rp,mid+1,r);
}

void buildWall(int N, int k, int o[], int l[], int r[], int h[], int ans[]){
    n = N;
    for(int i = 0; i <= 2*n; i++) seg[i]=Init;
    for(int i = 0; i < k; i++) upd(l[i],r[i],o[i]==1?h[i]:0,o[i]==1?mxN:h[i]);
    query(); for(int i = 0; i < n; i++) ans[i]=a[i];
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 8 ms 596 KB Output is correct
5 Correct 6 ms 596 KB Output is correct
6 Correct 6 ms 604 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 172 ms 8136 KB Output is correct
3 Correct 260 ms 4024 KB Output is correct
4 Correct 762 ms 20208 KB Output is correct
5 Correct 344 ms 21252 KB Output is correct
6 Correct 365 ms 19696 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 11 ms 596 KB Output is correct
5 Correct 9 ms 580 KB Output is correct
6 Correct 10 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 166 ms 8052 KB Output is correct
9 Correct 256 ms 4032 KB Output is correct
10 Correct 797 ms 20324 KB Output is correct
11 Correct 339 ms 21324 KB Output is correct
12 Correct 341 ms 19696 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 150 ms 13968 KB Output is correct
15 Correct 44 ms 1752 KB Output is correct
16 Correct 809 ms 20456 KB Output is correct
17 Correct 387 ms 19896 KB Output is correct
18 Correct 345 ms 19880 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 9 ms 596 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 6 ms 596 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 138 ms 8196 KB Output is correct
9 Correct 268 ms 4044 KB Output is correct
10 Correct 740 ms 20208 KB Output is correct
11 Correct 341 ms 21324 KB Output is correct
12 Correct 342 ms 19696 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 158 ms 13964 KB Output is correct
15 Correct 51 ms 1748 KB Output is correct
16 Correct 787 ms 20460 KB Output is correct
17 Correct 344 ms 19880 KB Output is correct
18 Correct 356 ms 19880 KB Output is correct
19 Correct 899 ms 75796 KB Output is correct
20 Correct 969 ms 73308 KB Output is correct
21 Correct 945 ms 75768 KB Output is correct
22 Correct 1004 ms 73332 KB Output is correct
23 Correct 971 ms 73376 KB Output is correct
24 Correct 922 ms 73412 KB Output is correct
25 Correct 918 ms 73256 KB Output is correct
26 Correct 966 ms 75736 KB Output is correct
27 Correct 972 ms 75864 KB Output is correct
28 Correct 935 ms 73388 KB Output is correct
29 Correct 903 ms 73212 KB Output is correct
30 Correct 895 ms 73252 KB Output is correct