oj.uz

Submission #308127

# Submission time Handle Problem Language Result Execution time Memory
308127 2020-09-30T04:51:53 Z ansol4328 Pyramid Base (IOI08_pyramid_base) C++14
70 / 100
 5000 ms 108704 KB 
#include<bits/stdc++.h>

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

struct SegTree{
    vector<ll> tree, lazy;
    int base;
    SegTree(int a){
        base=1;
        while(base<a) base<<=1;
        tree.resize(base*2+2);
        lazy.resize(base*2+2);
        base--;
    }
    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 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 ? lhs.y2<rhs.y2 : lhs.y1<rhs.y1;
}

int m, n, p;
ll b;
A ob[400005];
vector<int> in[1000005], out[1000005];
SegTree T(1000005);

bool pos(int w)
{
    T.setup(m-w+1);
    int idx=1, st, fn, k;
    for(int i=1 ; i<w ; i++){
        for(int k : in[i]){
            st=max(1,ob[k].x1-w+1);
            fn=min(m-w+1,ob[k].x2);
            T.add_value(ob[k].c,st,fn);
        }
    }
    for(int sy=1, fy=w ; fy<=n ; sy++, fy++){
        for(int k : in[fy]){
            st=max(1,ob[k].x1-w+1);
            fn=min(m-w+1,ob[k].x2);
            T.add_value(ob[k].c,st,fn);
        }
        for(int k : out[sy]){
            st=max(1,ob[k].x1-w+1);
            fn=min(m-w+1,ob[k].x2);
            T.add_value(-ob[k].c,st,fn);
        }
        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);
        in[ob[i].y1].push_back(i);
        out[ob[i].y2+1].push_back(i);
    }
    int st=1, fn=min(m,n), mid, ans=0;
    while(st<=fn){
        mid=(st+fn)>>1;
        if(pos(mid)) st=mid+1, ans=mid;
        else fn=mid-1;
    }
    printf("%d",ans);
    return 0;
}

Compilation message

pyramid_base.cpp: In function 'bool pos(int)':
pyramid_base.cpp:77:9: warning: unused variable 'idx' [-Wunused-variable]
   77 |     int idx=1, st, fn, k;
      |         ^~~
pyramid_base.cpp:77:24: warning: unused variable 'k' [-Wunused-variable]
   77 |     int idx=1, st, fn, k;
      |                        ^
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |     scanf("%d %d",&m,&n);
      |     ~~~~~^~~~~~~~~~~~~~~
pyramid_base.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |     scanf("%lld",&b);
      |     ~~~~~^~~~~~~~~~~
pyramid_base.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |     scanf("%d",&p);
      |     ~~~~~^~~~~~~~~
pyramid_base.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |         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 49 ms 80120 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 80120 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 80172 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 80248 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 80288 KB Output is correct
2 Correct 307 ms 80256 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 80248 KB Output is correct
2 Correct 197 ms 80248 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 80504 KB Output is correct
2 Correct 105 ms 80504 KB Output is correct
3 Correct 120 ms 80504 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 81440 KB Output is correct
2 Correct 616 ms 81400 KB Output is correct
3 Correct 520 ms 81272 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 81784 KB Output is correct
2 Correct 377 ms 80964 KB Output is correct
3 Correct 90 ms 81784 KB Output is correct
4 Correct 1486 ms 81820 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1063 ms 82168 KB Output is correct
2 Correct 1774 ms 81968 KB Output is correct
3 Correct 551 ms 82296 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 82680 KB Output is correct
2 Correct 2413 ms 82552 KB Output is correct
3 Correct 2156 ms 82468 KB Output is correct
4 Correct 2338 ms 82552 KB Output is correct
5 Correct 2131 ms 82552 KB Output is correct
6 Correct 429 ms 82552 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5067 ms 95480 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 5096 ms 102264 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 5056 ms 108704 KB Time limit exceeded
2 Halted 0 ms 0 KB -