Submission #588201

#	Time	Username	Problem	Language	Result	Execution time	Memory
588201		Bench0310	Pyramid Base (IOI08_pyramid_base)	C++17	70 / 100	5044 ms	106184 KiB

pyramid_base

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=1000005;
ll tree[4*N];
ll lazy[4*N];

void pull(int idx){tree[idx]=min(tree[2*idx],tree[2*idx+1]);}
void apply(int idx,ll x){tree[idx]+=x; lazy[idx]+=x;}
void push(int idx){for(int i=0;i<2;i++)apply(2*idx+i,lazy[idx]); lazy[idx]=0;}

void update(int idx,int l,int r,int ql,int qr,int x)
{
    if(ql>qr) return;
    if(l==ql&&r==qr) apply(idx,ll(x));
    else
    {
        int m=(l+r)/2;
        push(idx);
        update(2*idx,l,m,ql,min(qr,m),x);
        update(2*idx+1,m+1,r,max(ql,m+1),qr,x);
        pull(idx);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >> m >> n;
    int b,p;
    cin >> b >> p;
    vector<array<int,5>> obstacles(p);
    for(auto &[x1,y1,x2,y2,c]:obstacles) cin >> x1 >> y1 >> x2 >> y2 >> c;
    int l=0,r=min(n,m)+1;
    vector<array<int,3>> v[m+2];
    while(l<r-1)
    {
        int len=(l+r)/2;
        bool ok=0;
        int limm=m-len+1;
        int limn=n-len+1;
        auto add=[&](int x1,int y1,int x2,int y2,int c)
        {
            v[x1].push_back({y1,y2,c});
            v[x2+1].push_back({y1,y2,-c});
        };
        for(auto [x1,y1,x2,y2,c]:obstacles) add(max(1,x1-len+1),max(1,y1-len+1),min(x2,limm),min(y2,limn),c);
        for(int x=1;x<=limm+1;x++)
        {
            for(auto [y1,y2,c]:v[x]) update(1,1,limn,y1,y2,c);
            if(x<=limm) ok|=(tree[1]<=b);
            v[x].clear();
        }
        if(ok) l=len;
        else r=len;
    }
    cout << l << "\n";
    return 0;
}

• 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: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10