Submission #701661

#	Time	Username	Problem	Language	Result	Execution time	Memory
701661		Denkata	Wall (IOI14_wall)	C++14	61 / 100	982 ms	262144 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
const int maxn = 2e6;
struct seg
{
    ll mi,mx;
};
bool gen;
seg tree[maxn*4];
seg lz[maxn*4];
ll N,tek;
void pull_down(int p,ll val)
{
    lz[p].mi=min(lz[p].mi,val);
            lz[p].mx=min(lz[p].mx,val);
            tree[p].mi=min(tree[p].mi,val);
            tree[p].mx=min(tree[p].mx,val);
}
void pull_up(int p,ll val)
{
    lz[p].mx=max(lz[p].mx,val);
            lz[p].mi=max(lz[p].mi,val);
            tree[p].mi=max(tree[p].mi,val);
            tree[p].mx=max(tree[p].mx,val);
}
void push_lazy(int p)
{
    if(lz[p].mi!=LLONG_MIN)
    {
        if(p*2<=4*N)
            pull_up(p*2,lz[p].mi);
        if(p*2+1<=4*N)
            pull_up(p*2+1,lz[p].mi);
    }
    if(lz[p].mx!=LLONG_MAX)
    {
        if(p*2<=4*N)
            pull_down(p*2,lz[p].mx);
        if(p*2+1<=4*N)
            pull_down(p*2+1,lz[p].mx);
    }
    lz[p] = {LLONG_MIN,LLONG_MAX};
}
void update(int ql,int qr,int type,ll val,int p=1,int l=0,int r=N-1)
{
    //cout<<ql<<" "<<qr<<" "<<p<<" "<<l<<" "<<r<<endl;
    push_lazy(p);
    if(l>qr || r<ql)
        return ;
    if(l>=ql && r<=qr)
    {
        if(type==2)
        {
            pull_down(p,val);
        }
        else
        {
            pull_up(p,val);
        }
        return ;
    }
    update(ql,qr,type,val,p*2,l,(l+r)/2);
    update(ql,qr,type,val,p*2+1,(l+r)/2+1,r);
}
void query(int q,int p=1,int l=0,int r=N-1)
{
    push_lazy(p);
    if(q<l || q>r)
        return ;
    if(l==q && r==q)
    {
        tek = tree[p].mi;
        return ;
    }
    query(q,p*2,l,(l+r)/2);
    query(q,p*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;
    //cout<<"do tuka"<<endl;
    for(int i=0; i<k; i++)
    {
        if(op[i]==2)
            update(left[i],right[i],2,height[i]);///namalqvane => namirane na max stoinost
        else update(left[i],right[i],1,height[i]);///uvelichavane => namirane na min stoinost
    }
    for(int i=0; i<n; i++)
    {
        tek=0;
        query(i);
        finalHeight[i] = tek;
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 0 / 39