oj.uz

답안 #676311

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
676311 2022-12-30T09:17:16 Z alexdd 벽 (IOI14_wall) C++17
0 / 100
 132 ms 9476 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = LLONG_MAX;
struct node
{
    ll down_lim=0;
    ll up_lim=INF;
    ll last = 0;
    bool isProp = 1;
};
node aint[810001];
void upd(ll nod, ll st, ll dr, ll le, ll ri, ll tip, ll 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);
                if(aint[nod].up_lim < aint[nod].down_lim)
                    aint[nod].up_lim = aint[nod].down_lim;
            }
            else
            {
                aint[nod].up_lim = min(aint[nod].up_lim, newh);
                if(aint[nod].up_lim < aint[nod].down_lim)
                    aint[nod].down_lim = aint[nod].up_lim;
            }
        }
        return;
    }
    ll 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;
}
ll rez[200001];
void get_rez(ll nod, ll st, ll dr, ll sus, ll jos, bool done, ll 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;
    }
    ll 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 132 ms 9476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -