oj.uz

Submission #972835

# Submission time Handle Problem Language Result Execution time Memory
972835 2024-05-01T08:48:42 Z sleepntsheep Wall (IOI14_wall) C
0 / 100
 765 ms 26588 KB 
#include "wall.h"

#define MAX_N 2000002

int chmax[MAX_N<<2], chmin[MAX_N<<2], min[MAX_N<<2], max[MAX_N<<2];

void pull(int v)
{
    min[v]=min[v<<1|(min[v<<1]>min[v<<1|1])];
    max[v]=max[v<<1|(max[v<<1]<max[v<<1|1])];
}

void do_chmax(int v,int l,int r,int k)
{
    if(chmax[v]!=-1&&k<chmax[v])k=chmax[v];
    if(chmin[v]!=-1&&chmin[v]<=k){chmin[v]=-1,chmax[v]=k;}
    chmax[v]=k;
    if(k>=max[v])min[v]=max[v]=k;
    else if(k>=min[v])min[v]=k;
}

void do_chmin(int v,int l,int r,int k)
{
    if(chmin[v]!=-1&&k>chmin[v])k=chmin[v];
    if(chmax[v]!=-1&&chmax[v]>=k){chmax[v]=-1,chmin[v]=k;}
    chmin[v]=k;
    if(chmin[v]<min[v])min[v]=max[v]=chmin[v];
    else if(chmin[v]<max[v])max[v]=chmin[v];
}

void push(int v,int l,int r)
{
    if(chmin[v]!=-1)
    {
        if(l!=r) do_chmin(v<<1,l,l+(r-l)/2,chmin[v]),do_chmin(v<<1|1,l+(r-l)/2+1,r,chmin[v]);
        chmin[v]=-1;
    }
    if(chmax[v]!=-1)
    {
        if(l!=r) do_chmax(v<<1|1,l+(r-l)/2+1,r,chmax[v]),do_chmax(v<<1,l,l+(r-l)/2,chmax[v]);
        chmax[v]=-1;
    }
}

void do_do(int v,int l,int r,int x,int y,int k,void(*op)(int,int,int,int))
{
    push(v,l,r);
    if(r<x||y<l)return;
    if(x<=l&&r<=y){op(v,l,r,k);push(v,l,r);return ;}
    do_do(v<<1,l,l+(r-l)/2,x,y,k,op),do_do(v<<1|1,l+(r-l)/2+1,r,x,y,k,op);
    pull(v);
}

void build(int v,int l,int r)
{
    chmin[v]=chmax[v]=-1;
    if(l==r)min[v]=max[v]=0;
    else build(v<<1,l,l+(r-l)/2),build(v<<1|1,l+(r-l)/2+1,r),pull(v);
}

void ans(int v,int l,int r,int *o)
{
    push(v,l,r);
    if(l==r){o[l]=min[v];return;}
    ans(v<<1,l,l+(r-l)/2,o),ans(v<<1|1,l+(r-l)/2+1,r,o);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    build(1,0,n-1);
    for(int i=0;i<k;++i)
        if(op[i]==2)do_do(1,0,n-1,left[i],right[i],height[i],do_chmin);
        else do_do(1,0,n-1,left[i],right[i],height[i],do_chmax);
    ans(1,0,n-1,finalHeight);
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 110 ms 19972 KB Output is correct
3 Correct 262 ms 14740 KB Output is correct
4 Incorrect 765 ms 26588 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Incorrect 3 ms 6652 KB Output isn't correct
4 Halted 0 ms 0 KB -