oj.uz

Submission #465042

# Submission time Handle Problem Language Result Execution time Memory
465042 2021-08-14T23:12:49 Z nkato Wall (IOI14_wall) C++17
100 / 100
 1006 ms 99396 KB 
#include "wall.h"
 
#include<bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
 
using namespace std;
 
typedef pair<int,int> pii;
 
const int maxn=2e6+10;
pii seg[4*maxn];
int n;
 
pii comb(pii a,pii b){
    if(b==mp(-1,-1)) return a;
    pii ret=mp(min(a.xx,b.xx),max(a.yy,b.yy));
    if(ret.xx<ret.yy){
        if(ret.xx==a.xx) ret.yy=a.xx;
        else ret.xx=a.yy;
    }
    return ret;
}
 
void push(int ind){
    if(seg[ind]==mp(-1,-1)) return;
    seg[2*ind]=comb(seg[ind],seg[2*ind]);
    seg[2*ind+1]=comb(seg[ind],seg[2*ind+1]);
    seg[ind]=mp(-1,-1);
}
 
void update(int tl,int tr,int hg,int hd,int ind=1,int l=0,int r=n-1){
    if(l!=r) push(ind);
    if(tl<=l && r<=tr){
        seg[ind]=comb(mp(hg,hd),seg[ind]);
        return;
    }
    int mid=l+(r-l)/2;
    if(tl<=mid) update(tl,tr,hg,hd,2*ind,l,mid);
    if(tr>mid) update(tl,tr,hg,hd,2*ind+1,mid+1,r);
}
 
int query(int t,int ind=1,int l=0,int r=n-1){
    if(l!=r) push(ind);
    if(l==r) return seg[ind].xx;
    int mid=l+(r-l)/2;
    if(t<=mid) return query(t,2*ind,l,mid);
    if(t>mid) return query(t,2*ind+1,mid+1,r);
}
 
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    n=N;
    for(int i=0;i<4*maxn;i++) seg[i]=mp(-1,-1);
    update(0,n-1,0,0);
    for(int i=0;i<k;i++){
        if(op[i]==1){
            update(left[i],right[i],INT_MAX,height[i]);
        }else{
            update(left[i],right[i],height[i],INT_MIN);
        }
    }
    for(int i=0;i<n;i++) finalHeight[i]=query(i);
    return;
}

Compilation message

wall.cpp: In function 'int query(int, int, int, int)':
wall.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
   50 | }
      | ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 62788 KB Output is correct
2 Correct 38 ms 63016 KB Output is correct
3 Correct 35 ms 62964 KB Output is correct
4 Correct 42 ms 63096 KB Output is correct
5 Correct 37 ms 63052 KB Output is correct
6 Correct 39 ms 63080 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62896 KB Output is correct
2 Correct 189 ms 76444 KB Output is correct
3 Correct 260 ms 69956 KB Output is correct
4 Correct 772 ms 80868 KB Output is correct
5 Correct 340 ms 81936 KB Output is correct
6 Correct 320 ms 80372 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62788 KB Output is correct
2 Correct 35 ms 63004 KB Output is correct
3 Correct 34 ms 62916 KB Output is correct
4 Correct 41 ms 63152 KB Output is correct
5 Correct 38 ms 63092 KB Output is correct
6 Correct 39 ms 63044 KB Output is correct
7 Correct 34 ms 62804 KB Output is correct
8 Correct 188 ms 76448 KB Output is correct
9 Correct 282 ms 70084 KB Output is correct
10 Correct 785 ms 80884 KB Output is correct
11 Correct 354 ms 82000 KB Output is correct
12 Correct 319 ms 80324 KB Output is correct
13 Correct 33 ms 62788 KB Output is correct
14 Correct 201 ms 76612 KB Output is correct
15 Correct 73 ms 64088 KB Output is correct
16 Correct 786 ms 81144 KB Output is correct
17 Correct 366 ms 80592 KB Output is correct
18 Correct 324 ms 80580 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62820 KB Output is correct
2 Correct 34 ms 63048 KB Output is correct
3 Correct 35 ms 62908 KB Output is correct
4 Correct 41 ms 63096 KB Output is correct
5 Correct 40 ms 63052 KB Output is correct
6 Correct 38 ms 63080 KB Output is correct
7 Correct 33 ms 62788 KB Output is correct
8 Correct 195 ms 76488 KB Output is correct
9 Correct 277 ms 70004 KB Output is correct
10 Correct 798 ms 80832 KB Output is correct
11 Correct 342 ms 82112 KB Output is correct
12 Correct 339 ms 80328 KB Output is correct
13 Correct 34 ms 62924 KB Output is correct
14 Correct 194 ms 76488 KB Output is correct
15 Correct 75 ms 64016 KB Output is correct
16 Correct 783 ms 81316 KB Output is correct
17 Correct 332 ms 80548 KB Output is correct
18 Correct 323 ms 80652 KB Output is correct
19 Correct 994 ms 99208 KB Output is correct
20 Correct 1006 ms 96720 KB Output is correct
21 Correct 994 ms 99396 KB Output is correct
22 Correct 1002 ms 96768 KB Output is correct
23 Correct 999 ms 96760 KB Output is correct
24 Correct 983 ms 96748 KB Output is correct
25 Correct 988 ms 96984 KB Output is correct
26 Correct 1000 ms 99208 KB Output is correct
27 Correct 1006 ms 99268 KB Output is correct
28 Correct 984 ms 96668 KB Output is correct
29 Correct 987 ms 96836 KB Output is correct
30 Correct 978 ms 96800 KB Output is correct