제출 #289778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
289778		tasfiq4	벽 (IOI14_wall)	C++14	100 / 100	1010 ms	73336 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int > pii;
typedef long long int lld;
#define pi acos(-1)
#define fr(i,m,n) for(i=m;i<n;i++)
#define fu(i,m,n) for(i=m;i>=n;i--)
#define vec vector<int>
#define pb push_back
#define pp pop_back()
#define ft first
#define sd second
#define all(v) v.begin(),v.end()
#define mom(ara) memset(ara,0,sizeof(ara));
#define m1m(ara) memset(ara,-1,sizeof(ara));
#define endl "\n"
#define eps 1.19209e-07
#define at1 (at*2)
#define at2 (at*2)+1
// add is true and remove is false
int A[5000000],B[5000000];
bool opt[5000000],mark[5000000];
int ans;
void change(int at,int h,bool w)
{
    if(w)
    {
        if(h>A[at] || (!opt[at] && B[at]<h))
        {
            opt[at]=w;
            A[at]=h;
            mark[at]=true;
        }
    }
    else
    {
        if(h<B[at] || (opt[at] && A[at]>h))
        {
            opt[at]=w;
            B[at]=h;
            mark[at]=true;
        }
    }
}
void propagate(int l,int r,int at)
{
    mark[at]=false;
    if(opt[at])
    {
        change(at1,B[at],false);
        change(at2,B[at],false);
        change(at1,A[at],true);
        change(at2,A[at],true);
    }
    else
    {
        change(at1,A[at],true);
        change(at2,A[at],true);
        change(at1,B[at],false);
        change(at2,B[at],false);
    }
    A[at]=0;B[at]=1e9+7;
}
void update(int l,int r,int at,int L,int R,int h,bool w)
{
    if(l>R || r<L) return;
    if(L<=l && r<=R)
    {
        change(at,h,w);
        return;
    }
    if(mark[at]) propagate(l,r,at);
    int mid=(l+r)/2;
    update(l,mid,at1,L,R,h,w);
    update(mid+1,r,at2,L,R,h,w);
}
void query(int l,int r,int at,int pos)
{
    if(l==r)
    {
        if(mark[at])
        {
            if(opt[at])
            {
                ans=min(B[at],ans);
                ans=max(A[at],ans);
            }
            else
            {
                ans=max(A[at],ans);
                ans=min(B[at],ans);
            }
        }
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid) query(l,mid,at1,pos);
    else query(mid+1,r,at2,pos);
    if(mark[at])
    {
        if(opt[at])
            {
                ans=min(B[at],ans);
                ans=max(A[at],ans);
            }
            else
            {
                ans=max(A[at],ans);
                ans=min(B[at],ans);
            }
    }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    int i;
    fr(i,0,5000000) B[i]=1e9+7;
    fr(i,0,k)
    {
        update(1,n,1,left[i]+1,right[i]+1,height[i],(op[i]==1));
    }
    fr(i,1,n+1)
    {
        ans=0;
        query(1,n,1,i);
        finalHeight[i-1]=ans;
    }
    return;
}

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