Submission #1183538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183538		sleepntsheep	Pyramid Base (IOI08_pyramid_base)	C++20	0 / 100	2467 ms	78068 KiB

pyramid_base

#include <stdio.h>
#include <utility>
#include <algorithm>
#include <string.h>
#include <time.h>
#include <stdlib.h>

#define PP 400000

int m, n, b, p;

struct pyramid {
    int y1, x1, y2, x2, cost;
} a[PP + 1];


struct {

    long long t[4444444], lz[4444444];

    void pus(int v,int l,int r){
        if(lz[v]){
            t[v]+=lz[v];
            if(l-r){
                lz[v*2+1]+=lz[v];
                lz[v*2+2]+=lz[v];
            }
            lz[v]=0;
        }
    }

    void update(int v,int l,int r,int x,int y,int k){
        pus(v,l,r);
        if(r<x||y<l)return;
        if(x<=l&&r<=y){ lz[v]=k; pus(v,l,r);return; }
        update(v*2+1,l,(l+r)/2,x,y,k);update(v*2+2,(l+r)/2+1,r,x,y,k);
        t[v]=std::min(t[v*2+1],t[v*2+2]);
    }
    long long query(int v,int l,int r,int x,int y){
        pus(v,l,r);
        if(x<=l&&r<=y)return t[v];
        if(y<=(l+r)/2)return query(v*2+1,l,(l+r)/2,x,y);
        if(x>(l+r)/2)return query(v*2+2,(l+r)/2+1,r,x,y);
        return std::min(query(v*2+2,(l+r)/2+1,r,x,y),query(v*2+1,l,(l+r)/2,x,y));
    }
    void cl(){
        memset(t,0,sizeof t);
        memset(lz,0,sizeof lz);
    }
} s2;

int main() {
    srand(time(0));
    scanf("%d%d%d%d", &m, &n, &b, &p);
    for(int i=0;i<p;++i)
        scanf("%d%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2,&a[i].cost);


    if(1||b){
        static std::pair<int,int>ev[33333];

        int lower=-1,upper=std::min(n,m)+1;
        while(upper-lower>1){
            int mid=lower+(upper-lower)/2;

            for(int i=0;i<p;++i){
                ev[i*2]=std::make_pair(a[i].x1,i);
                ev[i*2+1]=std::make_pair(a[i].x2+mid,i|(1<<25));
            }
            std::sort(ev,ev+2*p);

            int i_{},found{};

            s2.cl();
            for(int i=1;!found&&i<=m;++i){
                while(i_<2*p&&ev[i_].first==i){
                    int i1{ev[i_].second};
                    if(i1>(1<<20)){
                        i1^=(1<<25);
                        s2.update(0,1,n,a[i1].y1,std::max(n,a[i1].y2+mid-1),-a[i1].cost);
                    }else{
                        s2.update(0,1,n,a[i1].y1,std::max(n,a[i1].y2+mid-1),a[i1].cost);
                    }
                    ++i_;
                }

                if(i>=mid){
                    found|=s2.query(0,1,n,mid,n)<=b;
                }
            }

            if(found)lower=mid;
            else upper=mid;
        }
        printf("%d\n",lower);
        return 0;
    }

    return 0;
}

Compilation message (stderr)

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d%d%d%d", &m, &n, &b, &p);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2,&a[i].cost);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10