oj.uz

Submission #758421

# Submission time Handle Problem Language Result Execution time Memory
758421 2023-06-14T15:22:34 Z Dan4Life Wall (IOI14_wall) C++17
100 / 100
 911 ms 57712 KB 
#include <bits/stdc++.h>
using namespace std;
const int mxN = (int)2e6+10;
int n;
array<int,2> seg[mxN*2], Init{0,mxN};

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 a[], 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; query(a,p+1,l,mid), query(a,p+2*(mid-l+1),mid+1,r);
}

void buildWall(int N, int k, int o[], int l[], int r[], int h[], int a[]){
    n = N; fill(seg,seg+2*n,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(a);
}

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 1 ms 212 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 10 ms 752 KB Output is correct
5 Correct 14 ms 724 KB Output is correct
6 Correct 6 ms 704 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 178 ms 13944 KB Output is correct
3 Correct 285 ms 7792 KB Output is correct
4 Correct 802 ms 10352 KB Output is correct
5 Correct 377 ms 10864 KB Output is correct
6 Correct 348 ms 10956 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 10 ms 668 KB Output is correct
5 Correct 6 ms 596 KB Output is correct
6 Correct 6 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 148 ms 13888 KB Output is correct
9 Correct 319 ms 7736 KB Output is correct
10 Correct 844 ms 10344 KB Output is correct
11 Correct 463 ms 10956 KB Output is correct
12 Correct 430 ms 10860 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 153 ms 8236 KB Output is correct
15 Correct 51 ms 1316 KB Output is correct
16 Correct 855 ms 10608 KB Output is correct
17 Correct 321 ms 10632 KB Output is correct
18 Correct 325 ms 10668 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 372 KB Output is correct
4 Correct 8 ms 668 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 6 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 143 ms 13904 KB Output is correct
9 Correct 265 ms 7632 KB Output is correct
10 Correct 713 ms 10348 KB Output is correct
11 Correct 322 ms 10904 KB Output is correct
12 Correct 349 ms 10864 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 146 ms 8212 KB Output is correct
15 Correct 47 ms 1316 KB Output is correct
16 Correct 815 ms 10600 KB Output is correct
17 Correct 327 ms 10676 KB Output is correct
18 Correct 321 ms 10612 KB Output is correct
19 Correct 911 ms 57624 KB Output is correct
20 Correct 877 ms 55152 KB Output is correct
21 Correct 886 ms 57712 KB Output is correct
22 Correct 891 ms 55292 KB Output is correct
23 Correct 873 ms 55148 KB Output is correct
24 Correct 901 ms 55112 KB Output is correct
25 Correct 905 ms 55148 KB Output is correct
26 Correct 882 ms 57644 KB Output is correct
27 Correct 896 ms 57624 KB Output is correct
28 Correct 871 ms 55240 KB Output is correct
29 Correct 884 ms 55096 KB Output is correct
30 Correct 869 ms 55244 KB Output is correct