Submission #625232

#	Time	Username	Problem	Language	Result	Execution time	Memory
625232		kakayoshi	Wall (IOI14_wall)	C++17	61 / 100	1082 ms	262144 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define forw(i,a,b) for(int i=a;i<=b;i++)
#define forb(i,a,b) for(int i=a;i>=b;i--)
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define getbit(mask,i) ((mask>>i)&1)
typedef long long int ll;
typedef pair<int,int> pii;
const ll maxN=2e6+5;
const ll mod=1e9+7;
const ll oo=1e18;
ll ans[maxN];
struct segment
{
    vector <ll> mi,ma;
    vector <pair<ll,ll>> lazy;
    segment(int n)
    {
        mi.assign(4*n+5,oo);
        ma.assign(4*n+5,-oo);
        lazy.assign(4*n+5,{-oo,oo});
    }
    void maxi(int id, ll h)
    {
        ma[id]=max(ma[id],h);
        mi[id]=max(ma[id],h);
        lazy[id].fi=max(lazy[id].fi,h);
        lazy[id].se=max(lazy[id].se,h);
        return;
    }
    void mini(int id, ll h)
    {
        ma[id]=min(ma[id],h);
        mi[id]=min(mi[id],h);
        lazy[id].fi=min(lazy[id].fi,h);
        lazy[id].se=min(lazy[id].se,h);
        return;
    }
    void down(int id)
    {
        maxi(id*2,lazy[id].fi);
        maxi(id*2+1,lazy[id].fi);
        mini(id*2,lazy[id].se);
        mini(id*2+1,lazy[id].se);
        lazy[id]={-oo,+oo};
        return;
    }
    void update(int id, int l, int r,int u, int v, int type, ll h) // 1 : add, 2: remove
    {
        if (v<l || r<u) return;
        if (u<=l && r<=v)
        {
            if (type==1) maxi(id,h);
            else mini(id,h);
            return;
        }
        down(id);
        int mid=(l+r)/2;
        update(id*2,l,mid,u,v,type,h);
        update(id*2+1,mid+1,r,u,v,type,h);
        ma[id]=ma[id*2];
        mi[id]=mi[id*2];
        maxi(id,ma[id*2+1]);
        mini(id,mi[id*2+1]);
        lazy[id]={-oo,oo};
        return;
    }
    void get_ans(int id, int l, int r)
    {
        if (l==r)
        {
            if (ma[id]==-oo) ans[l]=0;
            else ans[l]=ma[id];
            return;
        }
        down(id);
        int mid=(l+r)/2;
        get_ans(id*2,l,mid);
        get_ans(id*2+1,mid+1,r);
        return;
    }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    segment seg(n);
    forw(i,0,k-1)
        seg.update(1,1,n,left[i]+1,right[i]+1,op[i],height[i]);
    seg.get_ans(1,1,n);
    forw(i,0,n-1)
        finalHeight[i]=ans[i+1];
    return;
}
/*void solve()
{
    int n,q;
    cin>>n>>q;
    segment seg(n);
    while (q--)
    {
        int l,r,type,h;
        cin>>type>>l>>r>>h;
        l++;
        r++;
        seg.update(1,1,n,l,r,type,h);
    }
    seg.get_ans(1,1,n);
    forw(i,1,n) cout<<ans[i]<<"\n";
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    solve();
    return 0;
}*/

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