oj.uz

Submission #865970

# Submission time Handle Problem Language Result Execution time Memory
865970 2023-10-25T07:53:23 Z HuyQuang_re_Zero Pyramid Base (IOI08_pyramid_base) C++14
35 / 100
 5000 ms 134268 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; else c.lseg=0;
    if(b.r==c.mi) c.rseg=b.rseg+(b.full && b.r==a.r)*a.rseg; 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 47704 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 47708 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 47708 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 49772 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 56056 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 113752 KB Output is correct
2 Correct 534 ms 113500 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 113524 KB Output is correct
2 Correct 540 ms 113692 KB Output is correct

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 47704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 47708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 47708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 47708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 47964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5068 ms 124748 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 5027 ms 129632 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 5049 ms 134268 KB Time limit exceeded
2 Halted 0 ms 0 KB -