oj.uz

Submission #881186

# Submission time Handle Problem Language Result Execution time Memory
881186 2023-11-30T19:49:22 Z MarwenElarbi Wall (IOI14_wall) C++17
0 / 100
 135 ms 77068 KB 
#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "wall.h"
using namespace std;
const int nax = 2e6+5;
int lazy[nax*4][2];
int segtree[nax*4][2];
int tab[nax];
void expand(int pos){
    if(lazy[pos][0]!=-1){
        segtree[pos*2+1][0]=max(segtree[pos*2+1][0],lazy[pos][0]);
        segtree[pos*2+2][0]=max(segtree[pos*2+2][0],lazy[pos][0]);
        segtree[pos*2+1][1]=max(segtree[pos*2+1][1],lazy[pos][0]);
        segtree[pos*2+2][1]=max(segtree[pos*2+2][1],lazy[pos][0]);
        lazy[pos*2+1][0]=max(lazy[pos*2+1][0],lazy[pos][0]);
        lazy[pos*2+2][0]=max(lazy[pos*2+2][0],lazy[pos][0]);
        //lazy[pos*2+1][1]=max(lazy[pos*2+1][1],lazy[pos][0]);
        //lazy[pos*2+2][1]=max(lazy[pos*2+2][1],lazy[pos][0]);
    }
    if(lazy[pos][1]!=-1){
        segtree[pos*2+1][0]=min(segtree[pos*2+1][0],lazy[pos][1]);
        segtree[pos*2+2][0]=min(segtree[pos*2+2][0],lazy[pos][1]);
        segtree[pos*2+1][1]=min(segtree[pos*2+1][1],lazy[pos][1]);
        segtree[pos*2+2][1]=min(segtree[pos*2+2][1],lazy[pos][1]);
        lazy[pos*2+1][1]=lazy[pos*2+2][1]=1e9;
        lazy[pos*2+1][1]=min(lazy[pos*2+1][1],lazy[pos][1]);
        lazy[pos*2+2][1]=min(lazy[pos*2+2][1],lazy[pos][1]);
        //lazy[pos*2+1][0]=min(lazy[pos*2+1][0],lazy[pos][1]);
        //lazy[pos*2+2][0]=min(lazy[pos*2+2][0],lazy[pos][1]);
    }
    lazy[pos][0]=lazy[pos][1]=-1;
    return;
}
void update(int pos,int l,int r,int left,int right,int value,int type){
    if(l>r||l>right||r<left) return;
    if(l>=left&&r<=right){
        //expand(pos);
        if(type==1){
            if (segtree[pos][0]<value) lazy[pos][0]=value;
            segtree[pos][0]=max(segtree[pos][0],value);
            segtree[pos][1]=max(segtree[pos][1],value);
            //lazy[pos][1]=max(lazy[pos][1],value);
            
        }else{
            if (segtree[pos][1]>value) lazy[pos][1]=value;
            segtree[pos][1]=min(segtree[pos][1],value);
            segtree[pos][0]=min(segtree[pos][0],value);
            //lazy[pos][0]=min(segtree[pos][0],value);
            //cout <<l<<" "<<r<<" "<<segtree[pos][1]<<endl;
        }
        return;
    }
    //cout <<l<<" "<<r<<" "<<lazy[pos][0]<<" "<<lazy[pos][1]<<endl;
    expand(pos);
    int mid=(r+l)/2;
    update(pos*2+1,l,mid,left,right,value,type);
    update(pos*2+2,mid+1,r,left,right,value,type);
    segtree[pos][0]=min(segtree[pos*2+1][0],segtree[pos*2+2][0]);
    segtree[pos][1]=max(segtree[pos*2+1][1],segtree[pos*2+2][1]);
    //cout << l<<" "<<r<<" "<<segtree[pos][0]<<" "<<segtree[pos][1]<<endl;
    //cout <<l<<" "<<r<<" "<<segtree[pos][1]<<endl;
}
void build(int pos,int l,int r){
    if(l==r){
        tab[l]=segtree[pos][1];
        return;
    }
    expand(pos);
    int mid=(r+l)/2;
    build(pos*2+1,l,mid);
    build(pos*2+2,mid+1,r);
    segtree[pos][0]=min(segtree[pos*2+1][0],segtree[pos*2+2][0]);
    segtree[pos][1]=max(segtree[pos*2+1][1],segtree[pos*2+2][1]);
    return;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < nax*4; ++i)
    {
        lazy[i][0]=lazy[i][1]=-1;
    }
    for(int i=0;i<k;i++){
        if(op[i]==1){
            int l=left[i];
            int r=right[i];
            int x=height[i];
            update(0,0,n-1,l,r,x,1);
        }else{
            int l=left[i];
            int r=right[i];
            int x=height[i];
            update(0,0,n-1,l,r,x,2);
        }//cout <<endl;
    }//cout <<endl;
    build(0,0,n-1);
    for (int i = 0; i < n; ++i)
    {
        finalHeight[i]=tab[i];
    }
    return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 63324 KB Output is correct
2 Correct 14 ms 63580 KB Output is correct
3 Incorrect 13 ms 63580 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 63324 KB Output is correct
2 Correct 117 ms 77068 KB Output is correct
3 Incorrect 135 ms 71252 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 63320 KB Output is correct
2 Correct 13 ms 63680 KB Output is correct
3 Incorrect 13 ms 63580 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 63576 KB Output is correct
2 Correct 13 ms 63580 KB Output is correct
3 Incorrect 13 ms 63508 KB Output isn't correct
4 Halted 0 ms 0 KB -