oj.uz

Submission #1000783

# Submission time Handle Problem Language Result Execution time Memory
1000783 2024-06-18T08:43:32 Z bachhoangxuan Pyramid Base (IOI08_pyramid_base) C++17
100 / 100
 831 ms 194380 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
#define pii pair<int,int>
#define fi first
#define se second

int N,M,B,P,C[maxn];
struct Rec{
    int x,y,u,v;
}R[maxn];

namespace B1{
    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];
    }
    void solve(){
        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),u=R[i].u;
                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';
    }
}

namespace B0{
    vector<int> add[maxn],del[maxn];
    struct node{
        int val=0,sz=0,lt=0,rt=0,len=0;
        node(int s=0){
            sz=lt=rt=len=s;
        }
        friend node operator+(node a,node b){
            node res;
            res.len=a.len+b.len;
            res.val=min(a.val,b.val);
            if(a.val<b.val){
                res.sz=a.sz;
                res.lt=a.lt;
                res.rt=0;
            }
            else if(a.val>b.val){
                res.sz=b.sz;
                res.rt=b.rt;
                res.lt=0;
            }
            else{
                res.sz=max({a.sz,b.sz,a.rt+b.lt});
                res.lt=a.lt+(a.lt==a.len)*b.lt;
                res.rt=b.rt+(b.rt==b.len)*a.rt;
            }
            return res;
        }
    }tree[4*maxn];
    void build(int l,int r,int id){
        tree[id]=node(r-l+1);
        if(l==r) return;
        int mid=(l+r)>>1;
        build(l,mid,id<<1);build(mid+1,r,id<<1|1);
    }
    int lazy[4*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+=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]=tree[id<<1]+tree[id<<1|1];
        tree[id].val+=lazy[id];
    }
    void solve(){
        for(int i=1;i<=P;i++){
            add[R[i].x].push_back(i);
            del[R[i].u].push_back(i);
        }
        int res=0;
        build(1,M,1);
        for(int i=1,j=0;i<=N;i++){
            while(j<=N){
                if((!tree[1].val)*tree[1].sz<j-i+1) break;
                j++;
                for(int id:add[j]) update(1,M,1,R[id].y,R[id].v,1);
            }
            res=max(res,j-i);
            for(int id:del[i]) update(1,M,1,R[id].y,R[id].v,-1);
        }
        cout << res << '\n';
    }
}

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];
    if(B) B1::solve();
    else B0::solve();
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 149068 KB Output is correct

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 150052 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 153680 KB Output is correct
2 Correct 69 ms 154708 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 151972 KB Output is correct
2 Correct 65 ms 153916 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 149844 KB Output is correct
2 Correct 84 ms 149840 KB Output is correct
3 Correct 78 ms 149844 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 154452 KB Output is correct
2 Correct 230 ms 155220 KB Output is correct
3 Correct 189 ms 155256 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 171344 KB Output is correct
2 Correct 92 ms 154080 KB Output is correct
3 Correct 148 ms 181740 KB Output is correct
4 Correct 399 ms 187728 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 181912 KB Output is correct
2 Correct 610 ms 190832 KB Output is correct
3 Correct 155 ms 170048 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 173144 KB Output is correct
2 Correct 809 ms 193616 KB Output is correct
3 Correct 749 ms 193228 KB Output is correct
4 Correct 831 ms 193484 KB Output is correct
5 Correct 777 ms 193484 KB Output is correct
6 Correct 105 ms 170580 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 172628 KB Output is correct
2 Correct 214 ms 164948 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 178900 KB Output is correct
2 Correct 567 ms 183624 KB Output is correct
3 Correct 390 ms 175180 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 183628 KB Output is correct
2 Correct 813 ms 194380 KB Output is correct
3 Correct 831 ms 194124 KB Output is correct
4 Correct 727 ms 191808 KB Output is correct
5 Correct 570 ms 186144 KB Output is correct