oj.uz

Submission #588114

# Submission time Handle Problem Language Result Execution time Memory
588114 2022-07-02T17:38:27 Z Bench0310 Pyramid Base (IOI08_pyramid_base) C++17
70 / 100
 5000 ms 152044 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;
typedef long long ll;

const int N=1000005;
vector<ll> tree(4*N,0);
vector<ll> lazy(4*N,0);

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,ll x)
{
    if(ql>qr) return;
    if(l==ql&&r==qr) apply(idx,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<ll,3>> v[m+2];
    const ll inf=(1ll<<32);
    while(l<r-1)
    {
        int len=(l+r)/2;
        bool ok=0;
        auto add=[&](int x1,int y1,int x2,int y2,ll 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),x2,y2,c);
        if(len>1)
        {
            add(1,n-len+2,m,n,inf);
            add(m-len+2,1,m,n,inf);
        }
        for(int x=1;x<=m+1;x++)
        {
            for(auto [y1,y2,c]:v[x]) update(1,1,n,y1,y2,c);
            if(x<=m) ok|=(tree[1]<=b);
            v[x].clear();
        }
        if(ok) l=len;
        else r=len;
    }
    cout << l << "\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 62836 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62896 KB Output is correct

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 63348 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 65740 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 86780 KB Output is correct
2 Correct 149 ms 86888 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 87028 KB Output is correct
2 Correct 150 ms 86716 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 63964 KB Output is correct
2 Correct 81 ms 64200 KB Output is correct
3 Correct 71 ms 64232 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 68900 KB Output is correct
2 Correct 360 ms 69644 KB Output is correct
3 Correct 296 ms 69772 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 92440 KB Output is correct
2 Correct 142 ms 91800 KB Output is correct
3 Correct 299 ms 65468 KB Output is correct
4 Correct 1067 ms 96284 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1091 ms 95480 KB Output is correct
2 Correct 1067 ms 98844 KB Output is correct
3 Correct 862 ms 90568 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1111 ms 93852 KB Output is correct
2 Correct 1495 ms 101152 KB Output is correct
3 Correct 1450 ms 100832 KB Output is correct
4 Correct 1482 ms 101436 KB Output is correct
5 Correct 1432 ms 101060 KB Output is correct
6 Correct 884 ms 90116 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5018 ms 136312 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 5031 ms 144740 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 5058 ms 152044 KB Time limit exceeded
2 Halted 0 ms 0 KB -