Submission #865971

#	Time	Username	Problem	Language	Result	Execution time	Memory
865971		HuyQuang_re_Zero	Pyramid Base (IOI08_pyramid_base)	C++14	35 / 100	5083 ms	134228 KiB

pyramid_base

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 1000005
#define II pair <int,int>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
int n,m,type,lim;
struct IT_node
{
    int res,lz,l,r,lseg,rseg,mi;
    bool full;
    void modify(int k)
    {
        lz+=k; l+=k; r+=k; mi+=k;
    }
};
IT_node operator + (IT_node a,IT_node b)
{
    IT_node c;
    c.l=a.l; c.r=b.r; c.mi=min(a.mi,b.mi);
    c.full=(a.full && b.full && a.l==b.r);
    if(a.l==c.mi) c.lseg=a.lseg+((a.full && b.l==a.l) ? b.lseg : 0);
    else c.lseg=0;
    if(b.r==c.mi) c.rseg=b.rseg+((b.full && b.r==a.r) ? a.rseg : 0);
    else c.rseg=0;
    c.lz=c.res=0;
    if(a.mi==c.mi) c.res=max(c.res,a.res);
    if(b.mi==c.mi) c.res=max(c.res,b.res);
    if(a.r==c.mi && b.l==c.mi) c.res=max(c.res,a.rseg+b.lseg);
    return c;
}
struct Interval_Tree
{
    IT_node st[4*N];
    void build(int id,int l,int r)
    {
        if(l==r) { st[id]={ 1,0,0,0,1,1,0,1 }; return ; }
        int mid=(l+r)>>1,jd=id<<1;
        build(jd,l,mid); build(jd+1,mid+1,r);
        st[id]=st[jd]+st[jd+1];
    }
    void down(int id)
    {
        if(st[id].lz==0) return ;
        st[id<<1].modify(st[id].lz); st[(id<<1)+1].modify(st[id].lz);
        st[id].lz=0;
    }
    void update(int id,int l,int r,int u,int v,int k)
    {
        if(u<=l && r<=v) { st[id].modify(k); return ; }
        down(id);
        int mid=(l+r)>>1,jd=id<<1;
        if(v<=mid) update(jd,l,mid,u,v,k);
        else if(u>mid) update(jd+1,mid+1,r,u,v,k);
        else
        {
            update(jd,l,mid,u,mid,k);
            update(jd+1,mid+1,r,mid+1,v,k);
        }
        st[id]=st[jd]+st[jd+1];
    }
} IT;

struct SUB0
{
    int cnt,i;
    vector <II> L[N],R[N];
    bool check(int k)
    {
        IT.build(1,1,n);
        for(i=1;i<=m;i++)
        {
            for(II u:L[i]) IT.update(1,1,n,u.fst,u.snd,1);
            if(i>=k)
            {
                for(II u:R[i-k]) IT.update(1,1,n,u.fst,u.snd,-1);
                if(IT.st[1].mi==0 && IT.st[1].res>=k) return 1;
            }
        }
        return 0;
    }
    void Work()
    {
        cin>>cnt;
        while(cnt--)
        {
            int x1,y1,x2,y2,k;
            cin>>x1>>y1>>x2>>y2>>k;
            L[y1].push_back({ x1,x2 });
            R[y2].push_back({ x1,x2 });
        }
        int l=0,r=min(n,m);
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            if(check(mid)) l=mid; else r=mid-1;
        }
        cout<<l;
    }
} Sub0;
int main()
{
   // freopen("pyramid_base.inp","r",stdin);
 //   freopen("pyramid_base.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>lim;
    if(lim==0) Sub0.Work();
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10