oj.uz

Submission #676207

# Submission time Handle Problem Language Result Execution time Memory
676207 2022-12-29T20:28:06 Z alexdd Wall (IOI14_wall) C++17
0 / 100
 134 ms 8096 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = 1000000007;
struct node
{
    int down_lim=0;
    int up_lim=INF;
    int last = 0;
    bool isProp = 1;
};
node aint[810001];
void upd(int nod, int st, int dr, int le, int ri, int tip, int newh)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        if(tip==1)
        {
            aint[nod].last = tip;
            if(tip==1)
                aint[nod].down_lim = max(aint[nod].down_lim, newh);
            else
                aint[nod].up_lim = min(aint[nod].up_lim, newh);
        }
        return;
    }
    int mij=(st+dr)/2;
    upd(nod*2,st,mij,le,min(mij,ri),tip,newh);
    upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,tip,newh);
    aint[nod].last = -1;
}
int rez[200001];
void get_rez(int nod, int st, int dr, int sus, int jos, bool done, int lastval)
{
    if(!done && aint[nod].last != -1)
    {
        done = 1;
        if(aint[nod].last == 1)
            lastval = aint[nod].down_lim;
        else
            lastval = aint[nod].up_lim;
    }
    sus = min(sus, aint[nod].up_lim);
    jos = max(jos, aint[nod].down_lim);
    if(st==dr)
    {
        if(sus < jos)
        {
            rez[st] = lastval;
        }
        else
        {
            rez[st] = min(rez[st],sus);
            rez[st] = max(rez[st],jos);
        }
        return;
    }
    int mij=(st+dr)/2;
    get_rez(nod*2,st,mij,sus,jos,done,lastval);
    get_rez(nod*2,mij+1,dr,sus,jos,done,lastval);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for(int i=0;i<n;i++)
        rez[i] = 0;
    for(int i=0;i<k;i++)
    {
        upd(1,0,n-1,left[i],right[i],op[i],height[i]);
    }

    get_rez(1,0,n-1,INF,0,0,-1);
    for(int i=0;i<n;i++)
        finalHeight[i]=rez[i];
    return;
}
/**



*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 134 ms 8096 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -