oj.uz

답안 #969310

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
969310 2024-04-24T23:25:56 Z vjudge1 Pyramid Base (IOI08_pyramid_base) C++17
100 / 100
 1160 ms 185660 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m,b,p;
#define N 1<<20
#define M 7<<16
struct info{
    int minv,BA,BP,BS,SZ,lz;
    info(){minv=lz=BA=BP=BS=0;}
    info(int sz){minv=lz=0,BA=BP=BS=SZ=sz;}
    info(info a,info b){
        minv=min(a.minv,b.minv);
        if(minv-b.minv)
            *this=a,BS=0;
        else if(minv-a.minv)
            *this=b,BP=0;
        else {
            BA=max({a.BA,b.BA,a.BS+b.BP});
            BP=(a.BP==a.SZ?a.BP+b.BP:a.BP);
            BS=(b.BS==b.SZ?b.BS+a.BS:b.BS);
        }
        SZ=a.SZ+b.SZ,lz=0;
    }
} T[2*N];
void pd(int i,bool b){
    if(T[i].lz){
        T[i].minv+=T[i].lz;
        if(b)
            T[i*2].lz+=T[i].lz,T[i*2+1].lz+=T[i].lz;
        T[i].lz=0;
    }
}
void update(int i,int l,int r,int ql,int qr,int k){
    if(ql<=l&&r<=qr)
        return T[i].lz+=k,pd(i,l-r);
    pd(i,l-r);
    if(ql>r||l>qr)
        return;
    update(i*2,l,l+r>>1,ql,qr,k);
    update(i*2+1,l+r+2>>1,r,ql,qr,k);
    T[i]=info(T[i*2],T[i*2+1]);
}
void build(int i,int l,int r){
    T[i]=info(r-l+1);
    if(l-r) build(i*2,l,l+r>>1),
        build(i*2+1,l+r+2>>1,r);
}
vector<pair<int,int>> Add[N],Rem[N];
int calc2(){
    int ans=0,l=1,r=0;
    build(1,1,m);
    for(int i=0;i<p;i++){
        int a,b,c,d,e;
        cin>>a>>b>>c>>d>>e;
        Add[a].push_back({b,d});
        Rem[c].push_back({b,d});
    }
    while(r<=n){
        int A=r-l+1,B=T[1].BA*!T[1].minv;
        ans=max(ans,min(A,B));
        if(A<B){
            r++;
            for(auto[i,j]:Add[r])
                update(1,1,m,i,j,1);
        } else {
            for(auto[i,j]:Rem[l])
                update(1,1,m,i,j,-1);
            l++;
        }
    }
    return ans;
}
int S[2*N],B[2*N],A[M],B2[M],C[M],D[M],W[M],STUFF[N],SMTH[N],SMTH2[N];
void reset(int i,int l,int r){
    S[i]=B[i]=0;
    if(l==r) return void(STUFF[l]=i);
    reset(i*2,l,l+r>>1);
    reset(i*2+1,l+r+2>>1,r);
}
void add(int pos,int x){
    pos=STUFF[pos];
    S[pos]=B[pos]+=x;
    pos/=2;
    while(pos){
        S[pos]=S[pos*2]+S[pos*2+1];
        B[pos]=min(B[pos*2],B[pos*2+1]+S[pos*2]);
        pos/=2;
    }
}
vector<pair<int,int>>pref[2*N];
bool check(int k){
    for(int i=0;i<p;i++){
        int a=max(1,A[i]-k+1);
        int b=max(1,B2[i]-k+1);
        pref[a].push_back({b,W[i]});
        if(D[i]<=m-k+1)
            pref[a].push_back({D[i],-W[i]});
        if(C[i]<=n-k+1)
            pref[C[i]].push_back({b,-W[i]}),SMTH[C[i]]=1;
        if(D[i]<=m-k+1&&C[i]<=n-k+1)
            pref[C[i]].push_back({D[i],W[i]});
    }
    reset(1,1,m-k+1);
    int ans=0;
    for(int i=1;i<n-k+2;i++){
        for(auto [x,w]:pref[i])
            add(x,w);
        if(B[1]<=b) {
            ans=1;
            break;
        }
    }
    for(int i=1;i<=n-k+2;i++)
        pref[i].clear();
    return ans;
}
int calc(){
    b=min(b,7000*p);
    for(int i=0;i<p;i++)
        cin>>A[i]>>B2[i]>>C[i]>>D[i]>>W[i],C[i]++,D[i]++;
    if(!b) for(int i=0;i<p;i++)
        W[i]=1;
    int l=0,r=min(n,m);
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid))
            l=mid;
        else
            r=mid-1;
    }
    return l;
}
#undef N
#undef M
signed main(){
    //freopen("input.txt", "r", stdin);
    cin.tie(0)->sync_with_stdio(0);
    //long long XXX=chrono::steady_clock::now().time_since_epoch().count();
    cin>>n>>m>>b>>p;
    if(b)
        cout<<calc()<<'\n';
    else cout<<calc2()<<'\n';
    //long long YYY=chrono::steady_clock::now().time_since_epoch().count();
    //cerr<<fixed<<setprecision(10)<<"Took: "<<(YYY-XXX)/1e9<<'s';
}

Compilation message

pyramid_base.cpp: In function 'void update(int, int, int, int, int, int)':
pyramid_base.cpp:38:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     update(i*2,l,l+r>>1,ql,qr,k);
      |                  ~^~
pyramid_base.cpp:39:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     update(i*2+1,l+r+2>>1,r,ql,qr,k);
      |                  ~~~^~
pyramid_base.cpp: In function 'void build(int, int, int)':
pyramid_base.cpp:44:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     if(l-r) build(i*2,l,l+r>>1),
      |                         ~^~
pyramid_base.cpp:45:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |         build(i*2+1,l+r+2>>1,r);
      |                     ~~~^~
pyramid_base.cpp: In function 'void reset(int, int, int)':
pyramid_base.cpp:76:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |     reset(i*2,l,l+r>>1);
      |                 ~^~
pyramid_base.cpp:77:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |     reset(i*2+1,l+r+2>>1,r);
      |                 ~~~^~
pyramid_base.cpp: In function 'int calc()':
pyramid_base.cpp:124:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  124 |         int mid=l+r+1>>1;
      |                 ~~~^~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 148596 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 148564 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 148828 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 148968 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 148836 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 148820 KB Output is correct
2 Correct 58 ms 148820 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 148712 KB Output is correct
2 Correct 56 ms 148820 KB Output is correct

Subtask #8
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 149096 KB Output is correct
2 Correct 62 ms 149844 KB Output is correct
3 Correct 60 ms 149892 KB Output is correct

Subtask #9
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 154196 KB Output is correct
2 Correct 172 ms 154984 KB Output is correct
3 Correct 155 ms 154964 KB Output is correct

Subtask #10
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 294 ms 165796 KB Output is correct
2 Correct 97 ms 157520 KB Output is correct
3 Correct 143 ms 169712 KB Output is correct
4 Correct 505 ms 180940 KB Output is correct

Subtask #11
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 477 ms 178340 KB Output is correct
2 Correct 848 ms 183304 KB Output is correct
3 Correct 283 ms 163188 KB Output is correct

Subtask #12
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 407 ms 166388 KB Output is correct
2 Correct 1065 ms 185460 KB Output is correct
3 Correct 1002 ms 185300 KB Output is correct
4 Correct 1097 ms 185660 KB Output is correct
5 Correct 1160 ms 185612 KB Output is correct
6 Correct 192 ms 162580 KB Output is correct

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 486 ms 160160 KB Output is correct
2 Correct 296 ms 155060 KB Output is correct

Subtask #14
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 701 ms 165124 KB Output is correct
2 Correct 769 ms 169796 KB Output is correct
3 Correct 479 ms 162980 KB Output is correct

Subtask #15
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 784 ms 169864 KB Output is correct
2 Correct 1063 ms 178656 KB Output is correct
3 Correct 1029 ms 178404 KB Output is correct
4 Correct 1029 ms 176492 KB Output is correct
5 Correct 664 ms 171432 KB Output is correct