oj.uz

Submission #588264

# Submission time Handle Problem Language Result Execution time Memory
588264 2022-07-03T00:04:36 Z Bench0310 Pyramid Base (IOI08_pyramid_base) C++17
100 / 100
 1243 ms 208180 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

namespace S1
{
    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);
        }
    }
}

namespace S2
{
    const int N=1000005;
    struct node
    {
        int sz;
        int mn,len;
        int lx,lc,rx,rc;
        int lazy;
        void ini(int s){sz=s; mn=lx=rx=0; len=lc=rc=s; lazy=0;}
        friend node merge(node &a,node &b)
        {
            node c;
            c.sz=a.sz+b.sz;
            c.mn=min(a.mn,b.mn);
            c.len=0;
            if(a.mn==c.mn) c.len=max(c.len,a.len);
            if(b.mn==c.mn) c.len=max(c.len,b.len);
            if(a.rx==c.mn&&b.lx==c.mn) c.len=max(c.len,a.rc+b.lc);
            c.lx=a.lx;
            c.lc=(a.lc<a.sz?a.lc:a.lc+(a.lx==b.lx)*b.lc);
            c.rx=b.rx;
            c.rc=(b.rc<b.sz?b.rc:b.rc+(a.rx==b.rx)*a.rc);
            c.lazy=0;
            return c;
        }
        void apply(int x){mn+=x; lx+=x; rx+=x; lazy+=x;}
        void push(node &a,node &b){a.apply(lazy); b.apply(lazy); lazy=0;}
    };
    vector<node> tree(4*N);
    void build(int idx,int l,int r)
    {
        tree[idx].ini(r-l+1);
        if(l<r)
        {
            int m=(l+r)/2;
            build(2*idx,l,m);
            build(2*idx+1,m+1,r);
        }
    }
    void pull(int idx){tree[idx]=merge(tree[2*idx],tree[2*idx+1]);}
    void apply(int idx,int x){tree[idx].apply(x);}
    void push(int idx){tree[idx].push(tree[2*idx],tree[2*idx+1]);}
    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,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;
    if(b>0)
    {
        using namespace S1;
        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";
    }
    else
    {
        using namespace S2;
        int res=0;
        build(1,1,n);
        auto f=[&]()->int{return (tree[1].mn==0)*tree[1].len;};
        vector<array<int,2>> l[m+1],r[m+1];
        for(auto [x1,y1,x2,y2,c]:obstacles)
        {
            l[x1].push_back({y1,y2});
            r[x2].push_back({y1,y2});
        }
        int g=0;
        for(int i=1;i<=m;i++)
        {
            while(f()>=g-i+1)
            {
                res=max(res,g-i+1);
                if(g==m) break;
                g++;
                for(auto [y1,y2]:l[g]) update(1,1,n,y1,y2,1);
            }
            for(auto [y1,y2]:r[i]) update(1,1,n,y1,y2,-1);
        }
        cout << res << "\n";
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 125448 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 125492 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 125536 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 126016 KB Output is correct

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 172604 KB Output is correct
2 Correct 102 ms 172592 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 172612 KB Output is correct
2 Correct 109 ms 172488 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 127280 KB Output is correct
2 Correct 99 ms 127052 KB Output is correct
3 Correct 98 ms 127128 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 135624 KB Output is correct
2 Correct 314 ms 135428 KB Output is correct
3 Correct 254 ms 135848 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 173196 KB Output is correct
2 Correct 142 ms 153948 KB Output is correct
3 Correct 284 ms 161112 KB Output is correct
4 Correct 825 ms 191768 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 624 ms 192272 KB Output is correct
2 Correct 900 ms 194104 KB Output is correct
3 Correct 210 ms 173488 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 176244 KB Output is correct
2 Correct 1175 ms 196204 KB Output is correct
3 Correct 1148 ms 195892 KB Output is correct
4 Correct 1182 ms 196432 KB Output is correct
5 Correct 1156 ms 196340 KB Output is correct
6 Correct 137 ms 174444 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 188216 KB Output is correct
2 Correct 347 ms 182948 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 863 ms 195144 KB Output is correct
2 Correct 839 ms 191740 KB Output is correct
3 Correct 630 ms 143016 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 963 ms 201496 KB Output is correct
2 Correct 1243 ms 199228 KB Output is correct
3 Correct 1216 ms 199264 KB Output is correct
4 Correct 1105 ms 208180 KB Output is correct
5 Correct 771 ms 202976 KB Output is correct