oj.uz

Submission #587809

# Submission time Handle Problem Language Result Execution time Memory
587809 2022-07-02T11:42:01 Z yutabi Wall (IOI14_wall) C++14
100 / 100
 798 ms 69540 KB 
#include "wall.h"

#include <bits/stdc++.h>
using namespace std;




int N;

int mini[8000007];
int maxi[8000007];


void add_mini(int node, int val)
{
    if(val==-1)
    {
        return;
    }

    if(mini[node]==-1)
    {
        mini[node]=val;
    }

    mini[node]=max(mini[node],val);

    if(maxi[node]!=-1)
    {
        maxi[node]=max(mini[node],maxi[node]);
    }
}

void add_maxi(int node, int val)
{
    if(val==-1)
    {
        return;
    }
    
    if(maxi[node]==-1)
    {
        maxi[node]=val;
    }

    maxi[node]=min(maxi[node],val);

    if(mini[node]!=-1)
    {
        mini[node]=min(maxi[node],mini[node]);
    }
}


void update_mini(int hl, int hr, int h, int node=1, int l=0, int r=N-1)
{
    if(hl<=l && r<=hr)
    {
        add_mini(node,h);

        return;
    }

    add_mini(node*2,mini[node]);
    add_maxi(node*2,maxi[node]);
    
    add_mini(node*2+1,mini[node]);
    add_maxi(node*2+1,maxi[node]);

    mini[node]=-1;
    maxi[node]=-1;

    int m=(l+r)/2;

    if(hl<=m)
    {
        update_mini(hl,hr,h,node*2,l,m);
    }

    if(m+1<=hr)
    {
        update_mini(hl,hr,h,node*2+1,m+1,r);
    }
}


void update_maxi(int hl, int hr, int h, int node=1, int l=0, int r=N-1)
{
    if(hl<=l && r<=hr)
    {
        add_maxi(node,h);

        return;
    }

    add_mini(node*2,mini[node]);
    add_maxi(node*2,maxi[node]);
    
    add_mini(node*2+1,mini[node]);
    add_maxi(node*2+1,maxi[node]);

    mini[node]=-1;
    maxi[node]=-1;

    int m=(l+r)/2;

    if(hl<=m)
    {
        update_maxi(hl,hr,h,node*2,l,m);
    }

    if(m+1<=hr)
    {
        update_maxi(hl,hr,h,node*2+1,m+1,r);
    }
}

int* res;

void last(int node=1, int l=0, int r=N-1)
{
    if(l==r)
    {
        res[l]=mini[node];

        return;
    }

    add_mini(node*2,mini[node]);
    add_maxi(node*2,maxi[node]);
    
    add_mini(node*2+1,mini[node]);
    add_maxi(node*2+1,maxi[node]);

    mini[node]=-1;
    maxi[node]=-1;

    last(node*2,l,(l+r)/2);
    last(node*2+1,(l+r)/2+1,r);
}


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

    res=finalHeight;

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

        else
        {
            update_maxi(left[i],right[i],height[i]);
        }
    }

    last();


    return;
}

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 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 760 KB Output is correct
5 Correct 6 ms 828 KB Output is correct
6 Correct 5 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 196 ms 12156 KB Output is correct
3 Correct 189 ms 7912 KB Output is correct
4 Correct 566 ms 13872 KB Output is correct
5 Correct 292 ms 14108 KB Output is correct
6 Correct 310 ms 14776 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 3 ms 340 KB Output is correct
3 Correct 2 ms 368 KB Output is correct
4 Correct 6 ms 832 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 772 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 167 ms 12176 KB Output is correct
9 Correct 230 ms 7920 KB Output is correct
10 Correct 601 ms 13892 KB Output is correct
11 Correct 316 ms 14088 KB Output is correct
12 Correct 306 ms 14760 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 152 ms 12188 KB Output is correct
15 Correct 40 ms 1996 KB Output is correct
16 Correct 643 ms 14176 KB Output is correct
17 Correct 291 ms 14372 KB Output is correct
18 Correct 316 ms 14376 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 724 KB Output is correct
5 Correct 5 ms 720 KB Output is correct
6 Correct 5 ms 836 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 158 ms 12116 KB Output is correct
9 Correct 201 ms 7988 KB Output is correct
10 Correct 559 ms 14104 KB Output is correct
11 Correct 300 ms 14028 KB Output is correct
12 Correct 307 ms 14740 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 182 ms 12180 KB Output is correct
15 Correct 36 ms 1948 KB Output is correct
16 Correct 674 ms 14152 KB Output is correct
17 Correct 294 ms 14412 KB Output is correct
18 Correct 285 ms 14412 KB Output is correct
19 Correct 709 ms 61776 KB Output is correct
20 Correct 798 ms 66928 KB Output is correct
21 Correct 768 ms 69468 KB Output is correct
22 Correct 709 ms 66944 KB Output is correct
23 Correct 691 ms 66912 KB Output is correct
24 Correct 663 ms 66940 KB Output is correct
25 Correct 694 ms 66948 KB Output is correct
26 Correct 702 ms 69540 KB Output is correct
27 Correct 684 ms 69496 KB Output is correct
28 Correct 688 ms 67072 KB Output is correct
29 Correct 684 ms 66912 KB Output is correct
30 Correct 673 ms 66960 KB Output is correct