oj.uz

Submission #710223

# Submission time Handle Problem Language Result Execution time Memory
710223 2023-03-15T05:50:15 Z JJAnawat Wall (IOI14_wall) C++14
100 / 100
 988 ms 102440 KB 
#include "wall.h"
#include<bits/stdc++.h>

using namespace std;

const int inf=1e9;

struct node{
    int mn,mx;

    node(int mnn=-inf,int mxx=inf){
        mn=mnn;
        mx=mxx;
    }
};

node seg[(1<<22)];
node lz[(1<<22)];

void add(int i,int k){
    seg[i].mn=max(seg[i].mn,k);
    seg[i].mx=max(seg[i].mx,k);
    lz[i].mn=max(lz[i].mn,k);
    lz[i].mx=max(lz[i].mx,k);
}

void rem(int i,int k){
    seg[i].mn=min(seg[i].mn,k);
    seg[i].mx=min(seg[i].mx,k);
    lz[i].mn=min(lz[i].mn,k);
    lz[i].mx=min(lz[i].mx,k);
}

void push(int i){
    if(lz[i].mn!=-inf){
        add(2*i,lz[i].mn);
        add(2*i+1,lz[i].mn);
    }
    if(lz[i].mx!=inf){
        rem(2*i,lz[i].mx);
        rem(2*i+1,lz[i].mx);
    }
    lz[i]=node();
}

void upd(int l,int r,int i,int x,int y,int v,int op){
    if(l>y||r<x)
        return;
    if(l>=x&&r<=y){
        if(op==1)
            add(i,v);
        else
            rem(i,v);
        return;
    }
    push(i);
    int m=(l+r)/2;
    upd(l,m,2*i,x,y,v,op);
    upd(m+1,r,2*i+1,x,y,v,op);
    seg[i].mn=min(seg[2*i].mn,seg[2*i+1].mn);
    seg[i].mx=max(seg[2*i+1].mx,seg[2*i+1].mx);
}

int qr(int l,int r,int i,int x){
    if(l==r)
        return seg[i].mn;
    int m=(l+r)/2;
    push(i);
    if(x<=m)
        return qr(l,m,2*i,x);
    else
        return qr(m+1,r,2*i+1,x);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i=0;i<(1<<22);i++)
        seg[i]=node(0,0);
    for(int i=0;i<k;i++)
        upd(0,n-1,1,left[i],right[i],height[i],op[i]);
    for(int i=0;i<n;i++)
        finalHeight[i]=qr(0,n-1,1,i);
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65860 KB Output is correct
2 Correct 38 ms 65904 KB Output is correct
3 Correct 34 ms 65980 KB Output is correct
4 Correct 40 ms 66068 KB Output is correct
5 Correct 39 ms 66052 KB Output is correct
6 Correct 39 ms 66108 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65844 KB Output is correct
2 Correct 152 ms 73804 KB Output is correct
3 Correct 227 ms 69276 KB Output is correct
4 Correct 566 ms 74304 KB Output is correct
5 Correct 324 ms 74860 KB Output is correct
6 Correct 311 ms 74816 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 65952 KB Output is correct
2 Correct 38 ms 65932 KB Output is correct
3 Correct 35 ms 65936 KB Output is correct
4 Correct 41 ms 66132 KB Output is correct
5 Correct 39 ms 66028 KB Output is correct
6 Correct 39 ms 66016 KB Output is correct
7 Correct 34 ms 65852 KB Output is correct
8 Correct 150 ms 73880 KB Output is correct
9 Correct 202 ms 69324 KB Output is correct
10 Correct 574 ms 74556 KB Output is correct
11 Correct 362 ms 74796 KB Output is correct
12 Correct 308 ms 74800 KB Output is correct
13 Correct 35 ms 65944 KB Output is correct
14 Correct 153 ms 73724 KB Output is correct
15 Correct 70 ms 66572 KB Output is correct
16 Correct 654 ms 74600 KB Output is correct
17 Correct 334 ms 74672 KB Output is correct
18 Correct 318 ms 74568 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 65876 KB Output is correct
2 Correct 39 ms 66000 KB Output is correct
3 Correct 46 ms 65964 KB Output is correct
4 Correct 41 ms 65996 KB Output is correct
5 Correct 43 ms 66036 KB Output is correct
6 Correct 42 ms 66064 KB Output is correct
7 Correct 35 ms 65928 KB Output is correct
8 Correct 160 ms 73780 KB Output is correct
9 Correct 207 ms 69320 KB Output is correct
10 Correct 680 ms 74312 KB Output is correct
11 Correct 473 ms 74884 KB Output is correct
12 Correct 336 ms 74820 KB Output is correct
13 Correct 33 ms 65900 KB Output is correct
14 Correct 165 ms 73704 KB Output is correct
15 Correct 73 ms 66556 KB Output is correct
16 Correct 673 ms 74640 KB Output is correct
17 Correct 340 ms 74624 KB Output is correct
18 Correct 357 ms 74560 KB Output is correct
19 Correct 988 ms 91808 KB Output is correct
20 Correct 887 ms 99860 KB Output is correct
21 Correct 908 ms 102340 KB Output is correct
22 Correct 926 ms 99864 KB Output is correct
23 Correct 883 ms 99888 KB Output is correct
24 Correct 849 ms 99912 KB Output is correct
25 Correct 871 ms 99916 KB Output is correct
26 Correct 876 ms 102440 KB Output is correct
27 Correct 859 ms 102300 KB Output is correct
28 Correct 854 ms 99868 KB Output is correct
29 Correct 857 ms 99864 KB Output is correct
30 Correct 857 ms 99996 KB Output is correct