oj.uz

Submission #492732

# Submission time Handle Problem Language Result Execution time Memory
492732 2021-12-08T15:14:39 Z Carmel_Ab1 Wall (IOI14_wall) C++17
100 / 100
 1220 ms 111628 KB 
#include<bits/stdc++.h>
using namespace std;


#include "wall.h"

const int maxn=4e6+1;

int t[2*maxn],L[2*maxn],R[2*maxn],propmx[2*maxn],propmn[2*maxn];




inline void build(int x,int tl,int tr){
    L[x]=tl;
    R[x]=tr;
    propmn[x]=1e9;
    propmx[x]=-1e9;
    if(tl+1==tr)return;

    int m=(L[x]+R[x])/2;
    build(2*x+1,tl,m);
    build(2*x+2,m,tr);
}

inline void applymn(int x,int v){
    propmx[x]=min(propmx[x],v);
    propmn[x]=min(propmn[x],v);
    t[x]=min(t[x],v);
}

inline void applymx(int x,int v){
    propmx[x]=max(propmx[x],v);
    propmn[x]=max(propmn[x],v);
    t[x]=max(t[x],v);
}

inline void push(int x){
    int lp=2*x+1,rp=2*x+2;

    applymn(lp,propmn[x]);
    applymn(rp,propmn[x]);
    propmn[x]=1e9;

    applymx(lp,propmx[x]);
    applymx(rp,propmx[x]);
    propmx[x]=-1e9;
}

inline void updmn(int x,int a,int b,int v){
    int l=L[x],r=R[x];
    if(r<=a || b<=l)
        return;
    else if(a<=l && r<=b){
        applymn(x,v);
        return;
    }
    push(x);
    updmn(2*x+1,a,b,v);
    updmn(2*x+2,a,b,v);
}
inline void updmx(int x,int a,int b,int v){
    int l=L[x],r=R[x];
    if(r<=a || b<=l)
        return;
    else if(a<=l && r<=b){
        applymx(x,v);
        return;
    }
    push(x);
    updmx(2*x+1,a,b,v);
    updmx(2*x+2,a,b,v);
}
inline int qur(int i,int x){
    int l=L[x],r=R[x];
    int m=(l+r)/2;
    if(l+1==r)
        return t[x];
    push(x);
    if(i<m)
        return qur(i,2*x+1);
    else
        return qur(i,2*x+2);
}

void buildWall(int n, int k, int op[], int LL[], int RR[], int H[], int ans[]){

    build(0,0,n);

    for(int i=0; i<k; i++){
        if(op[i]==1)
            updmx(0,LL[i],RR[i] +1,H[i]);
        else
            updmn(0,LL[i],RR[i] +1,H[i]);
    }
    for(int i=0; i<n; i++)
        ans[i]=qur(i,0);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 428 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 1084 KB Output is correct
5 Correct 6 ms 1100 KB Output is correct
6 Correct 7 ms 1100 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 131 ms 8284 KB Output is correct
3 Correct 181 ms 5060 KB Output is correct
4 Correct 512 ms 14052 KB Output is correct
5 Correct 285 ms 14448 KB Output is correct
6 Correct 289 ms 14488 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 400 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 1144 KB Output is correct
5 Correct 9 ms 1056 KB Output is correct
6 Correct 7 ms 1120 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 122 ms 8244 KB Output is correct
9 Correct 166 ms 5076 KB Output is correct
10 Correct 483 ms 14108 KB Output is correct
11 Correct 284 ms 14416 KB Output is correct
12 Correct 277 ms 14448 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 123 ms 8288 KB Output is correct
15 Correct 28 ms 2320 KB Output is correct
16 Correct 499 ms 14204 KB Output is correct
17 Correct 282 ms 14192 KB Output is correct
18 Correct 281 ms 14156 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 9 ms 1124 KB Output is correct
5 Correct 6 ms 1228 KB Output is correct
6 Correct 6 ms 1100 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 127 ms 8260 KB Output is correct
9 Correct 170 ms 5040 KB Output is correct
10 Correct 537 ms 13968 KB Output is correct
11 Correct 288 ms 14532 KB Output is correct
12 Correct 299 ms 14436 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 126 ms 8224 KB Output is correct
15 Correct 34 ms 2244 KB Output is correct
16 Correct 545 ms 14208 KB Output is correct
17 Correct 299 ms 14388 KB Output is correct
18 Correct 286 ms 14204 KB Output is correct
19 Correct 1139 ms 111628 KB Output is correct
20 Correct 1124 ms 109252 KB Output is correct
21 Correct 1130 ms 111556 KB Output is correct
22 Correct 1141 ms 108916 KB Output is correct
23 Correct 1115 ms 108900 KB Output is correct
24 Correct 1136 ms 109008 KB Output is correct
25 Correct 1220 ms 109020 KB Output is correct
26 Correct 1139 ms 111352 KB Output is correct
27 Correct 1123 ms 111312 KB Output is correct
28 Correct 1132 ms 108808 KB Output is correct
29 Correct 1137 ms 108744 KB Output is correct
30 Correct 1125 ms 108680 KB Output is correct