oj.uz

Submission #567674

# Submission time Handle Problem Language Result Execution time Memory
567674 2022-05-24T02:45:13 Z Jesus Wall (IOI14_wall) C++14
100 / 100
 590 ms 77536 KB 
#include "wall.h"
#include<bits/stdc++.h>

using namespace std;

int lim;

pair<int,int> st[8000001];

pair<int,int> reiniciar={0,1000000000};

void heredar(int pos){
    for(int i=pos*2;i<=pos*2+1;i++){
        st[i].second=min(st[i].second,st[pos].second);
        if(st[pos].second<=st[i].first) st[i].first=max(st[pos].second,st[pos].first);
        else st[i].first=max(st[i].first,st[pos].first);
    }
    st[pos]=reiniciar;
}

void iniciar(int i=0,int j=lim-1,int pos=1){
    if(i==j) st[pos]=reiniciar;
    else{
        iniciar(i,(i+j)/2);
        iniciar((i+j)/2+1,j);
    }
}

void st_actualizar(int tp,int alt,int izq,int der,int i=0,int j=lim-1,int pos=1){
    if(izq==i&&der==j){
            if(tp==2){
                st[pos].second=min(st[pos].second,alt);
                if(st[pos].first>0) st[pos].first=min(st[pos].first,alt);
            }
            else st[pos].first=max(st[pos].first,alt);
    }
    else{
        if(st[pos].first>0||st[pos].second<1000000000) heredar(pos);
        if(izq<=(i+j)/2) st_actualizar(tp,alt,izq,min(der,(i+j)/2),i,(i+j)/2,pos*2);
        if(der>(i+j)/2) st_actualizar(tp,alt,max(izq,(i+j)/2+1),der,(i+j)/2+1,j,pos*2+1);
    }
    return;
}

int resultado[2000000];

void revision(int i=0,int j=lim-1,int pos=1){
    if(i==j){
        resultado[i]=st[pos].first;
    }
    else{
        if(st[pos].first>0||st[pos].second<1000000000) heredar(pos);
        revision(i,(i+j)/2,pos*2);
        revision((i+j)/2+1,j,pos*2+1);
    }
    return;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    lim=n; iniciar();

    for(int i=0;i<k;i++){
        st_actualizar(op[i],height[i],left[i],right[i]);
    }

    revision();

    for(int i=0;i<n;i++){
        finalHeight[i]=resultado[i];
    }

  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 448 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 4 ms 760 KB Output is correct
6 Correct 4 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 135 ms 13936 KB Output is correct
3 Correct 144 ms 8040 KB Output is correct
4 Correct 413 ms 20700 KB Output is correct
5 Correct 208 ms 21820 KB Output is correct
6 Correct 219 ms 20236 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 2 ms 388 KB Output is correct
4 Correct 8 ms 852 KB Output is correct
5 Correct 4 ms 760 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 150 ms 13964 KB Output is correct
9 Correct 154 ms 7964 KB Output is correct
10 Correct 369 ms 20696 KB Output is correct
11 Correct 243 ms 21760 KB Output is correct
12 Correct 187 ms 20196 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 155 ms 13888 KB Output is correct
15 Correct 36 ms 1996 KB Output is correct
16 Correct 471 ms 20956 KB Output is correct
17 Correct 258 ms 20464 KB Output is correct
18 Correct 199 ms 20392 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 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 852 KB Output is correct
5 Correct 5 ms 828 KB Output is correct
6 Correct 4 ms 836 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 129 ms 13856 KB Output is correct
9 Correct 134 ms 8012 KB Output is correct
10 Correct 412 ms 20792 KB Output is correct
11 Correct 204 ms 21792 KB Output is correct
12 Correct 216 ms 20264 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 131 ms 13864 KB Output is correct
15 Correct 27 ms 2012 KB Output is correct
16 Correct 472 ms 20956 KB Output is correct
17 Correct 282 ms 20440 KB Output is correct
18 Correct 199 ms 20504 KB Output is correct
19 Correct 542 ms 77536 KB Output is correct
20 Correct 516 ms 74824 KB Output is correct
21 Correct 528 ms 77332 KB Output is correct
22 Correct 556 ms 74960 KB Output is correct
23 Correct 537 ms 74936 KB Output is correct
24 Correct 501 ms 74752 KB Output is correct
25 Correct 529 ms 75000 KB Output is correct
26 Correct 590 ms 77268 KB Output is correct
27 Correct 572 ms 77448 KB Output is correct
28 Correct 534 ms 74832 KB Output is correct
29 Correct 516 ms 74816 KB Output is correct
30 Correct 529 ms 74832 KB Output is correct