oj.uz

Submission #310240

# Submission time Handle Problem Language Result Execution time Memory
310240 2020-10-06T12:26:19 Z ansol4328 Pyramid Base (IOI08_pyramid_base) C++14
100 / 100
 2251 ms 76540 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const ll INF=1e18;

struct Node{
    int maxv, lmax, rmax, lz, s, f;
    Node() : maxv(0), lmax(0), rmax(0), lz(0), s(0), f(0) {}
    Node& operator=(const Node &rhs){
        maxv=rhs.maxv, lmax=rhs.lmax, rmax=rhs.rmax;
        lz=rhs.lz;
        return *this;
    }
    Node operator+(const Node &rhs) const{
        Node ret;
        ret.maxv=max(maxv,rhs.maxv);
        ret.maxv=max(ret.maxv,rmax+rhs.lmax);
        ret.lmax=lmax, ret.rmax=rhs.rmax;
        if(lmax==f-s+1) ret.lmax+=rhs.lmax;
        if(rhs.rmax==rhs.f-rhs.s+1) ret.rmax+=rmax;
        return ret;
    }
};

struct SegTree{
    vector<ll> tree, lazy;
    int base;
    SegTree(){
        tree.resize(2097155);
        lazy.resize(2097155);
    }
    void setup(int a){
        base=1;
        while(base<a) base<<=1;
        for(int i=1 ; i<base*2 ; i++) tree[i]=lazy[i]=0;
        for(int i=base+a ; i<base*2 ; i++) tree[i]=INF;
        for(int i=base-1 ; i>=1 ; i--) tree[i]=min(tree[i*2],tree[i*2+1]);
        base--;
        
    }
    void propagate(int ns, int nf, int num){
        if(lazy[num]!=0){
            if(ns<nf){
                lazy[num*2]+=lazy[num];
                lazy[num*2+1]+=lazy[num];
            }
            tree[num]+=lazy[num];
            lazy[num]=0;
        }
    }
    ll query(int ns=1, int nf=-1, int num=1){
        if(nf==-1) nf=base+1;
        propagate(ns,nf,num);
        return tree[num];
    }
    void add_value(ll val, int st, int fn, int ns=1, int nf=-1, int num=1){
        if(nf==-1) nf=base+1;
        propagate(ns,nf,num);
        if(ns>fn || nf<st) return;
        if(st<=ns && nf<=fn){
            lazy[num]+=val;
            propagate(ns,nf,num);
            return;
        }
        int mid=(ns+nf)>>1;
        add_value(val,st,fn,ns,mid,num*2);
        add_value(val,st,fn,mid+1,nf,num*2+1);
        tree[num]=min(tree[num*2],tree[num*2+1]);
    }
};

struct SegTree2{
    vector<Node> tree;
    int base;
    SegTree2(){
        tree.resize(2097155);
    }
    void setup(int a){
        base=1;
        while(base<a) base<<=1;
        for(int i=base+a-1 ; i>=base ; i--) tree[i].maxv=tree[i].rmax=tree[i].lmax=1, tree[i].s=tree[i].f=i-base+1;
        for(int i=base-1 ; i>=1 ; i--){
            tree[i]=tree[i*2]+tree[i*2+1];
            tree[i].s=tree[i*2].s;
            tree[i].f=tree[i*2+1].f;
        }
        base--;
    }
    int query(int ns=1, int nf=-1, int num=1){
        return tree[num].maxv;
    }
    void update(int val, int st, int fn, int ns=1, int nf=-1, int num=1){
        if(nf==-1) nf=base+1;
        if(ns>fn || nf<st) return;
        if(st<=ns && nf<=fn){
            tree[num].lz+=val;
            if(tree[num].lz) tree[num].maxv=tree[num].lmax=tree[num].rmax=0;
            else if(ns<nf) tree[num]=tree[num*2]+tree[num*2+1];
            else if(ns==nf) tree[num].maxv=tree[num].lmax=tree[num].rmax=1;
            return;
        }
        int mid=(ns+nf)>>1;
        update(val,st,fn,ns,mid,num*2);
        update(val,st,fn,mid+1,nf,num*2+1);
        if(tree[num].lz) tree[num].maxv=tree[num].lmax=tree[num].rmax=0;
        else tree[num]=tree[num*2]+tree[num*2+1];
    }
};

struct A{
    int x1, y1, x2, y2, c;
    A(){}
    A(int t1, int t2, int t3, int t4, int t5) : x1(t1), y1(t2), x2(t3), y2(t4), c(t5) {}
};

bool cmp(const A &lhs, const A &rhs){
    return lhs.y1<rhs.y1;
}

bool cmp2(const A &lhs, const A &rhs){
    return lhs.y2<rhs.y2;
}

int m, n, p;
ll b;
A ob[400005], ob2[400005];

bool pos(SegTree &T, int w)
{
    T.setup(m-w+1);
    int idx=1, idx2=1, st, fn, k;
    for(int sy=1, fy=w ; fy<=n ; sy++, fy++){
        while(idx<=p && ob[idx].y1>=sy && ob[idx].y1<=fy){
            st=max(1,ob[idx].x1-w+1);
            fn=min(m-w+1,ob[idx].x2);
            T.add_value(ob[idx].c,st,fn);
            idx++;
        }
        while(idx2<=p && ob2[idx2].y2<sy){
            st=max(1,ob2[idx2].x1-w+1);
            fn=min(m-w+1,ob2[idx2].x2);
            T.add_value(-ob2[idx2].c,st,fn);
            idx2++;
        }
        if(T.query()<=b) return true;
    }
    return false;
}

int main()
{
    scanf("%d %d",&m,&n);
    scanf("%lld",&b);
    scanf("%d",&p);
    for(int i=1 ; i<=p ; i++){
        scanf("%d %d %d %d %d",&ob[i].x1,&ob[i].y1,&ob[i].x2,&ob[i].y2,&ob[i].c);
        ob2[i]=ob[i];
    }
    sort(ob+1,ob+1+p,cmp);
    sort(ob2+1,ob2+1+p,cmp2);
    if(b){
        SegTree T;
        int st=1, fn=min(m,n), mid, ans=0;
        while(st<=fn){
            mid=(st+fn)>>1;
            if(pos(T,mid)) st=mid+1, ans=mid;
            else fn=mid-1;
        }
        printf("%d",ans);
        return 0;
    }
    int idx1=1, idx2=1, ans=0;
    SegTree2 T2;
    T2.setup(m);
    for(int s=1, f=1 ; s<=n ; s++){
        for( ; idx1<=p && ob[idx1].y1<=f ; idx1++) T2.update(1,ob[idx1].x1,ob[idx1].x2);
        while(f<=n && f-s+1<=T2.query()){
            ans=max(ans,f-s+1);
            f++;
            for( ; idx1<=p && ob[idx1].y1<=f ; idx1++) T2.update(1,ob[idx1].x1,ob[idx1].x2);
        }
        if(f>n) ans=max(ans,min(f-s,T2.query()));
        for( ; idx2<=p && ob2[idx2].y2<=s ; idx2++) T2.update(-1,ob2[idx2].x1,ob2[idx2].x2);
    }
    printf("%d",ans);
    return 0;
}

Compilation message

pyramid_base.cpp: In function 'bool pos(SegTree&, int)':
pyramid_base.cpp:133:32: warning: unused variable 'k' [-Wunused-variable]
  133 |     int idx=1, idx2=1, st, fn, k;
      |                                ^
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:154:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  154 |     scanf("%d %d",&m,&n);
      |     ~~~~~^~~~~~~~~~~~~~~
pyramid_base.cpp:155:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  155 |     scanf("%lld",&b);
      |     ~~~~~^~~~~~~~~~~
pyramid_base.cpp:156:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  156 |     scanf("%d",&p);
      |     ~~~~~^~~~~~~~~
pyramid_base.cpp:158:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  158 |         scanf("%d %d %d %d %d",&ob[i].x1,&ob[i].y1,&ob[i].x2,&ob[i].y2,&ob[i].c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 49664 KB Output is correct

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 49664 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 49784 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 49784 KB Output is correct
2 Correct 51 ms 49664 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 49664 KB Output is correct
2 Correct 56 ms 49664 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 33408 KB Output is correct
2 Correct 65 ms 33408 KB Output is correct
3 Correct 77 ms 33408 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 33792 KB Output is correct
2 Correct 510 ms 33912 KB Output is correct
3 Correct 408 ms 33928 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 34048 KB Output is correct
2 Correct 333 ms 33912 KB Output is correct
3 Correct 46 ms 33912 KB Output is correct
4 Correct 1304 ms 34040 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 840 ms 34296 KB Output is correct
2 Correct 1590 ms 34296 KB Output is correct
3 Correct 358 ms 34168 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 34404 KB Output is correct
2 Correct 2149 ms 34400 KB Output is correct
3 Correct 1912 ms 34552 KB Output is correct
4 Correct 2251 ms 34424 KB Output is correct
5 Correct 2062 ms 34404 KB Output is correct
6 Correct 234 ms 34296 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 57592 KB Output is correct
2 Correct 530 ms 62712 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 868 ms 61432 KB Output is correct
2 Correct 961 ms 69624 KB Output is correct
3 Correct 470 ms 69240 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1046 ms 65412 KB Output is correct
2 Correct 1394 ms 76536 KB Output is correct
3 Correct 1428 ms 76276 KB Output is correct
4 Correct 1254 ms 76280 KB Output is correct
5 Correct 880 ms 76540 KB Output is correct