Submission #1000671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000671		bachhoangxuan	Pyramid Base (IOI08_pyramid_base)	C++17	80 / 100	5048 ms	106956 KiB

pyramid_base

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;

int N,M,B,P,C[maxn];
struct Rec{
    int x,y,u,v;
}R[maxn];
int tree[4*maxn],lazy[4*maxn];
vector<int> pos[maxn];

void update(int l,int r,int id,int tl,int tr,int val){
    if(tr<l || r<tl) return;
    if(tl<=l && r<=tr){
        tree[id]+=val;
        lazy[id]+=val;
        return;
    }
    int mid=(l+r)>>1;
    update(l,mid,id<<1,tl,tr,val);update(mid+1,r,id<<1|1,tl,tr,val);
    tree[id]=min(tree[id<<1],tree[id<<1|1])+lazy[id];
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> N >> M >> B >> P;
    for(int i=1;i<=P;i++) cin >> R[i].x >> R[i].y >> R[i].u >> R[i].v >> C[i];
    auto check = [&](int d){
        for(int i=1;i<=N-d+1;i++) pos[i].clear();
        for(int i=1;i<=4*(M-d+1);i++) tree[i]=lazy[i]=0;
        for(int i=1;i<=P;i++){
            int x=max(1,R[i].x-d+1),y=max(1,R[i].y-d+1),u=R[i].u,v=R[i].v;
            pos[x].push_back(i);pos[u+1].push_back(i);
        }
        for(int i=1;i<=N-d+1;i++){
            for(int id:pos[i]){
                int l=max(1,R[id].y-d+1),r=R[id].v,c=C[id];
                if(i==R[id].u+1) c=-c;
                update(1,M-d+1,1,l,r,c);
            }
            //cout << i << ' ' << tree[1] << '\n';
            if(tree[1]<=B) return true;
        }
        return false;
    };
    int l=1,r=min(N,M),res=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) res=mid,l=mid+1;
        else r=mid-1;
    }
    cout << res << '\n';
}

Compilation message (stderr)

pyramid_base.cpp: In lambda function:
pyramid_base.cpp:33:37: warning: unused variable 'y' [-Wunused-variable]
   33 |             int x=max(1,R[i].x-d+1),y=max(1,R[i].y-d+1),u=R[i].u,v=R[i].v;
      |                                     ^
pyramid_base.cpp:33:66: warning: unused variable 'v' [-Wunused-variable]
   33 |             int x=max(1,R[i].x-d+1),y=max(1,R[i].y-d+1),u=R[i].u,v=R[i].v;
      |                                                                  ^

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