제출 #1137122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137122		LeonidCuk	벽 (IOI14_wall)	C++20	0 / 100	3096 ms	197212 KiB

wall

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>lazy[8000001];
vector<int>v;
void smeni(int i,int k1)
{
    for(int j=0;j<lazy[i].size();j++)
    {
        if(lazy[i][j].first==1)v[k1]=max(v[k1],lazy[i][j].second);
        else v[k1]=min(v[k1],lazy[i][j].second);
    }
}
void add(int i,int i1)
{
    for(int j=0;j<lazy[i].size();j++)
    {
        auto p=lazy[i][j];
        if(lazy[i1].size()==0)lazy[i1].push_back(p);
        else if(lazy[i1].size()==1)
        {
            if(lazy[i1][0].first!=p.first)lazy[i1].push_back(p);
            else if(lazy[i1][0].first==1)lazy[i1][0].second=max(lazy[i1][0].second,p.second);
            else lazy[i1][0].second=min(lazy[i1][0].second,p.second);
        }
        else
        {
            if(lazy[i1][1].first==p.first)
            {
                if(lazy[i1][1].first==1)lazy[i1][1].second=max(lazy[i1][1].second,p.second);
                else lazy[i1][1].second=min(lazy[i1][1].second,p.second);
            }
            else
            {
                if(lazy[i1][0].second>p.second&&p.first==2)
                {
                    lazy[i1][0].second=p.second;
                    swap(lazy[i1][0],lazy[i1][1]);
                }
                else if(lazy[i1][0].second<p.second&&p.first==1)
                {
                    lazy[i1][0].second=p.second;
                    swap(lazy[i1][0],lazy[i1][1]);
                }
            }
        }
        if(lazy[i1].size()==2)
        {
            if(lazy[i1][0].second>lazy[i1][1].second&&lazy[i1][0].first==1)lazy[i1][0].second=lazy[i1][1].second;
            else if(lazy[i1][0].second<lazy[i1][1].second&&lazy[i1][0].first==2)lazy[i1][0].second=lazy[i1][1].second;
        }
    }
}
void update(int i,int l,int r,int tl,int tr,int k,int k1)
{
    if(l>r||tl>r||l>tr)
    {
        return;
    }
    if(!lazy[i].empty())
    {
        if(l==r)
        {
            smeni(i,l);
        }
        else
        {
            add(i,i*2);
            add(i,i*2+1);
            lazy[i].clear();
        }
    }
    if(tl<=l&&r<=tr)
    {
        lazy[i].push_back({k,k1});
        return;
    }
    int m=(l+r)/2;
    update(i*2,l,m,tl,tr,k,k1);
    update(i*2+1,m+1,r,tl,tr,k,k1);
}
void najdi(int i,int l,int r)
{
    if(!lazy[i].empty())
    {
        if(l==r)
        {
            smeni(i,l);
        }
        else
        {
            add(i,i*2);
            add(i,i*2+1);
            lazy[i].clear();
        }
    }
    if(l==r)return;
    int m=(l+r)/2;
    najdi(i*2,l,m);
    najdi(i*2+1,m+1,r);
}
void buildWall(int n, int m, int op[], int left[], int right[],int height[], int finalHeight[])
{
    v.resize(n);
    int a,b,c,d;
    for(int i=0;i<m;i++)
    {
        a=op[i];
        b=left[i];
        c=right[i];
        d=height[i];
        update(1,0,n-1,b,c,a,d);
    }
    najdi(1,0,n-1);
    for(int i=0;i<n;i++)finalHeight[i]=v[i];
}

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