oj.uz

Submission #588199

# Submission time Handle Problem Language Result Execution time Memory
588199 2022-07-02T18:54:44 Z Bench0310 Pyramid Base (IOI08_pyramid_base) C++17
70 / 100
 5000 ms 99468 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int N=1000001;
ll t[2000002];
ll d[1000001];
int h;

void apply(int p,ll val)
{
    t[p]+=val;
    if(p<N) d[p]+=val;
}

void build(int p)
{
    while(p>1){p/=2; t[p]=min(t[2*p],t[2*p+1])+d[p];}
}

void push(int p)
{
    for(int s=h;s>0;s--)
    {
        int i=(p>>s);
        if(d[i]!=0)
        {
            apply(2*i,d[i]);
            apply(2*i+1,d[i]);
            d[i]=0;
        }
    }
}

void update(int l,int r,ll val)
{
    l+=N; r+=(N+1);
    int l0=l,r0=r;
    for(;l<r;l/=2,r/=2)
    {
        if(l&1) apply(l++,val);
        if(r&1) apply(--r,val);
    }
    build(l0);
    build(r0-1);
}

ll query(int l,int r)
{
    l+=N; r+=(N+1);
    push(l);
    push(r-1);
    ll res=(1ll<<32);
    for(;l<r;l/=2,r/=2)
    {
        if(l&1) res=min(res,t[l++]);
        if(r&1) res=min(res,t[--r]);
    }
    return res;
}

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;
        N=limn;
        h=32-__builtin_clz(N);
        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(y1,y2,c);
            if(x<=limm) ok|=(query(1,limn)<=b);
            v[x].clear();
        }
        memset(t,0,sizeof(t));
        memset(d,0,sizeof(d));
        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 25 ms 23808 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23804 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 23884 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 24172 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 26528 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 47748 KB Output is correct
2 Correct 1472 ms 47856 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1385 ms 47776 KB Output is correct
2 Correct 532 ms 47656 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 25204 KB Output is correct
2 Correct 100 ms 24872 KB Output is correct
3 Correct 107 ms 24924 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 29788 KB Output is correct
2 Correct 403 ms 29808 KB Output is correct
3 Correct 313 ms 30300 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 919 ms 55100 KB Output is correct
2 Correct 234 ms 52428 KB Output is correct
3 Correct 186 ms 26780 KB Output is correct
4 Correct 1768 ms 57524 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1265 ms 57884 KB Output is correct
2 Correct 1910 ms 59576 KB Output is correct
3 Correct 658 ms 55436 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 57904 KB Output is correct
2 Correct 2211 ms 61716 KB Output is correct
3 Correct 2238 ms 61408 KB Output is correct
4 Correct 2207 ms 62028 KB Output is correct
5 Correct 2261 ms 61868 KB Output is correct
6 Correct 411 ms 56244 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5077 ms 86420 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 5076 ms 92620 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 5099 ms 99468 KB Time limit exceeded
2 Halted 0 ms 0 KB -