oj.uz

Submission #866112

# Submission time Handle Problem Language Result Execution time Memory
866112 2023-10-25T12:37:44 Z HuyQuang_re_Zero Pyramid Base (IOI08_pyramid_base) C++14
70 / 100
 5000 ms 196896 KB 
#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;


struct SUB1
{
    ll st[4*N],lz[4*N],p,i;
    struct pt { int l,r,k; };
    vector <pt> L[N],R[N];
    struct rec { int x1,y1,x2,y2,k; } a[N];
    void modify(int id,int k)
    {
        st[id]+=k;
        lz[id]+=k;
    }
    void down(int id)
    {
        modify(id*2,lz[id]); modify(id*2+1,lz[id]);
        lz[id]=0;
    }
    void update(int id,int l,int r,int u,int v,int k)
    {
        if(u>r || v<l) return ;
        if(u<=l && r<=v) { modify(id,k); return ; }
        down(id);
        int mid=(l+r)>>1;
        update(id*2,l,mid,u,v,k); update(id*2+1,mid+1,r,u,v,k);
        st[id]=min(st[id*2],st[id*2+1]);
    }
    bool check(int k)
    {
        for(i=1;i<=m;i++) L[i].clear(),R[i].clear();
        for(i=1;i<=p;i++)
        {
            int x1=a[i].x1,y1=a[i].y1,x2=min(n,a[i].x2+k-1),y2=min(m,a[i].y2+k-1);
            L[y1].push_back({ x1,x2,a[i].k });
            R[y2].push_back({ x1,x2,a[i].k });
        }
        memset(st,0,sizeof(st));
        memset(lz,0,sizeof(lz));
        for(i=1;i<=m;i++)
        {
            for(pt u:L[i]) update(1,k,n,u.l,u.r,u.k);
            if(i>=k)
            {
                if(st[1]<=lim) return 1;
            }
            for(pt u:R[i]) update(1,k,n,u.l,u.r,-u.k);
        }
        return 0;
    }
    void Work()
    {
        cin>>p;
        for(i=1;i<=p;i++) cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2>>a[i].k;
      //  check(5); return ;
        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;
    }
} Sub1;
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();
    else Sub1.Work();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 98908 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 98908 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 98904 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 100956 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 107224 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 164684 KB Output is correct
2 Correct 563 ms 164692 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 164696 KB Output is correct
2 Correct 556 ms 164680 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 161232 KB Output is correct
2 Correct 103 ms 161252 KB Output is correct
3 Correct 106 ms 161104 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 163412 KB Output is correct
2 Correct 319 ms 164032 KB Output is correct
3 Correct 259 ms 163864 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 165952 KB Output is correct
2 Correct 135 ms 161876 KB Output is correct
3 Correct 119 ms 165456 KB Output is correct
4 Correct 694 ms 169716 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 168992 KB Output is correct
2 Correct 823 ms 171656 KB Output is correct
3 Correct 364 ms 163696 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 166924 KB Output is correct
2 Correct 1025 ms 174104 KB Output is correct
3 Correct 958 ms 174072 KB Output is correct
4 Correct 1077 ms 174024 KB Output is correct
5 Correct 957 ms 174060 KB Output is correct
6 Correct 337 ms 163580 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5041 ms 181588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5022 ms 189520 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5029 ms 196896 KB Time limit exceeded
2 Halted 0 ms 0 KB -