oj.uz

Submission #866393

# Submission time Handle Problem Language Result Execution time Memory
866393 2023-10-26T04:31:38 Z HuyQuang_re_Zero Pyramid Base (IOI08_pyramid_base) C++14
100 / 100
 1187 ms 196516 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];
    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 });
        }
        IT.build(1,1,n);
        int j=1,res=0;
        for(i=1;i<=m;i++)
        {
            for(II u:L[i]) IT.update(1,1,n,u.fst,u.snd,1);
            while(IT.st[1].mi>0 || IT.st[1].res<i-j+1)
            {
                for(II u:R[j]) IT.update(1,1,n,u.fst,u.snd,-1);
                j++;
            }
            res=max(res,i-j+1);
        }
        cout<<res;
    }
} 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;
        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 23 ms 98908 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 107060 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 164176 KB Output is correct
2 Correct 65 ms 164020 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 164184 KB Output is correct
2 Correct 64 ms 164084 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 160848 KB Output is correct
2 Correct 108 ms 161104 KB Output is correct
3 Correct 127 ms 161288 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 163536 KB Output is correct
2 Correct 306 ms 163932 KB Output is correct
3 Correct 282 ms 164004 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 165972 KB Output is correct
2 Correct 145 ms 161876 KB Output is correct
3 Correct 129 ms 165588 KB Output is correct
4 Correct 711 ms 169640 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 168984 KB Output is correct
2 Correct 844 ms 171600 KB Output is correct
3 Correct 375 ms 163764 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 166924 KB Output is correct
2 Correct 1068 ms 174176 KB Output is correct
3 Correct 990 ms 174160 KB Output is correct
4 Correct 1029 ms 174220 KB Output is correct
5 Correct 973 ms 174148 KB Output is correct
6 Correct 337 ms 163276 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 181212 KB Output is correct
2 Correct 383 ms 173572 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 188892 KB Output is correct
2 Correct 780 ms 185848 KB Output is correct
3 Correct 453 ms 124328 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 817 ms 196516 KB Output is correct
2 Correct 1184 ms 193312 KB Output is correct
3 Correct 1187 ms 193252 KB Output is correct
4 Correct 1029 ms 192732 KB Output is correct
5 Correct 757 ms 186600 KB Output is correct