Submission #871756

#	Time	Username	Problem	Language	Result	Execution time	Memory
871756		HuyQuang_re_Zero	Wall (IOI14_wall)	C++14	0 / 100	1 ms	2396 KiB

wall

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "wall.h"
using namespace std;
const int m=100000;
int n,q,L[500001],R[500001],op[500001],H[500001],i,res[2000005];
struct Interval_Tree
{
    II st[8000005];
    void change(int id,II x)
    {
        if(x.fst>st[id].snd) st[id]={ x.fst,x.fst };
        else if(x.snd<st[id].fst) st[id]={ x.snd,x.snd };
        else st[id]={ max(st[id].fst,x.fst),min(st[id].snd,x.snd) };
    }
    void down(int id)
    {
        change(id*2,st[id]); change(id*2+1,st[id]);
        st[id]={ 0,m };
    }
    void build(int id,int l,int r)
    {
        if(l==r) { st[id]={ 0,0 }; return ; }
        int mid=(l+r)>>1;
        build(id*2,l,mid); build(id*2+1,mid+1,r);
        st[id]={ 0,m };
    }
    void update(int id,int l,int r,int u,int v,int x,int y)
    {
        if(u>r || v<l) return ;
        if(u<=l && r<=v) { change(id,{ x,y }); return ; }
        down(id);
        int mid=(l+r)>>1;
        update(id*2,l,mid,u,v,x,y); update(id*2+1,mid+1,r,u,v,x,y);
    }
    int get(int id,int l,int r,int u)
    {
        if(l==r) return st[id].fst;
        down(id);
        int mid=(l+r)>>1;
        if(u<=mid) return get(id*2,l,mid,u);
        return get(id*2+1,mid+1,r,u);
    }
} IT;
void buildWall(int n,int q,int op[],int L[],int R[],int H[],int res[])
{
    IT.build(1,1,n);
    for(i=0;i<q;i++)
    {
        L[i]++; R[i]++;
        if(op[i]==0) IT.update(1,1,n,L[i],R[i],H[i],m);
        else IT.update(1,1,n,L[i],R[i],0,H[i]);
    }
    for(i=0;i<n;i++) res[i]=IT.get(1,1,n,i+1);
}
/*
int main()
{
    freopen("wall.inp","r",stdin);
    freopen("wall.out","w",stdout);
    cin>>n>>q;
    for(i=0;i<q;i++) cin>>op[i]>>L[i]>>R[i]>>H[i];
    buildWall(n,q,op,L,R,H,res);
    for(i=0;i<n;i++) cout<<res[i]<<" ";
}
*/

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