oj.uz

답안 #905255

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
905255 2024-01-12T21:32:53 Z alexander707070 푸드 코트 (JOI21_foodcourt) C++14
13 / 100
 1000 ms 148624 KB 
#include<bits/stdc++.h>
#define MAXN 500007
using namespace std;

struct event{
    int c,tim;
    long long k;
};

const long long inf=1e17;

int n,m,q,type,l,r;
long long s,t;

long long minsz[4*MAXN],lazy[4*MAXN],maxsz[4*MAXN];
int c[MAXN];

vector< event > tree[4*MAXN];
vector<long long> pref[4*MAXN];

void update(int v,int l,int r,int ll,int rr,event news){
    if(ll>rr)return;
    if(l==ll and r==rr){
        tree[v].push_back(news);

        if(pref[v].empty())pref[v].push_back(news.k);
        else pref[v].push_back(pref[v].back()+news.k);

        return;
    }else{
        int tt=(l+r)/2;
        update(2*v,l,tt,ll,min(tt,rr),news);
        update(2*v+1,tt+1,r,max(tt+1,ll),rr,news);
    }
}

void psh(int v){
    minsz[2*v]+=lazy[v];
    maxsz[2*v]+=lazy[v];

    minsz[2*v]=max(minsz[2*v],0LL);
    maxsz[2*v]=max(maxsz[2*v],0LL);

    minsz[2*v+1]+=lazy[v];
    maxsz[2*v+1]+=lazy[v];

    minsz[2*v+1]=max(minsz[2*v+1],0LL);
    maxsz[2*v+1]=max(maxsz[2*v+1],0LL);

    lazy[2*v]+=lazy[v];
    lazy[2*v+1]+=lazy[v];

    lazy[v]=0;
}

void add(int v,int l,int r,int ll,int rr,long long val){
    if(ll>rr)return;
    psh(v);

    if(l==ll and r==rr){

        minsz[v]+=val;
        maxsz[v]+=val;

        lazy[v]+=val;
    }else{
        int tt=(l+r)/2;
        add(2*v,l,tt,ll,min(tt,rr),val);
        add(2*v+1,tt+1,r,max(tt+1,ll),rr,val);

        minsz[v]=min(minsz[2*v],minsz[2*v+1]);
        maxsz[v]=max(maxsz[2*v],maxsz[2*v+1]);
    }
}

void rem(int v,int l,int r,int ll,int rr,long long val){
    if(ll>rr)return;
    psh(v);

    if(l==ll and r==rr and minsz[v]>=val){
        minsz[v]-=val;
        lazy[v]-=val;
        return;
    }

    if(l==ll and r==rr and maxsz[v]<=val){
        minsz[v]=maxsz[v]=0;
        lazy[v]=-inf;
        return;
    }

    if(l==r){
        minsz[v]=max(minsz[v]-val,0LL);
        maxsz[v]=max(maxsz[v]-val,0LL);     
    }else{
        int tt=(l+r)/2;
        rem(2*v,l,tt,ll,min(tt,rr),val);
        rem(2*v+1,tt+1,r,max(tt+1,ll),rr,val);

        minsz[v]=min(minsz[2*v],minsz[2*v+1]);
        maxsz[v]=max(maxsz[2*v],maxsz[2*v+1]);
    }
}

long long getsz(int v,int l,int r,int pos){
    if(l==r)return minsz[v];

    psh(v);
    int tt=(l+r)/2;

    if(pos<=tt)return getsz(2*v,l,tt,pos);
    else return getsz(2*v+1,tt+1,r,pos);
}

long long calc(int v,int qr){
    if(tree[v].empty())return 0;

    int l=-1,r=tree[v].size(),tt;

    while(l+1<r){
        tt=(l+r)/2;
        if(tree[v][tt].tim>=qr){
            r=tt;
        }else{
            l=tt;
        }
    }

    if(r>0)return pref[v].back()-pref[v][r-1];
    return pref[v].back();
}

long long howmany(int v,int l,int r,int pos,int qr){
    if(l==r){
        return calc(v,qr);
    }else{
        int tt=(l+r)/2;
        if(pos<=tt)return howmany(2*v,l,tt,pos,qr) + calc(v,qr);
        else return howmany(2*v+1,tt+1,r,pos,qr) + calc(v,qr);
    }
}

int bin(int s,long long t){
    int l=0,r=q+1,tt;
    while(l+1<r){
        tt=(l+r)/2;
        if(howmany(1,1,n,s,tt)>=t){
            l=tt;
        }else{
            r=tt;
        }
    }

    return c[l];
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>m>>q;
    
    for(int i=1;i<=q;i++){
        cin>>type;
        if(type==1){
            cin>>l>>r>>s>>t;
            c[i]=s;

            add(1,1,n,l,r,t);
            for(int i=l;i<=r;i++){
               // minsz[i]+=t;
            }

            update(1,1,n,l,r,{s,i,t});
        }else if(type==2){
            cin>>l>>r>>s;
            rem(1,1,n,l,r,s);
            for(int i=l;i<=r;i++){
               // minsz[i]=max(minsz[i]-s,0LL);
            }
        }else{
            cin>>s>>t;
            if(getsz(1,1,n,s)<t)cout<<"0\n";
            else cout<<bin(s,getsz(1,1,n,s)-t+1)<<"\n";
        }
    }

    return 0;
}

Compilation message

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:176:31: warning: narrowing conversion of 's' from 'long long int' to 'int' [-Wnarrowing]
  176 |             update(1,1,n,l,r,{s,i,t});
      |                               ^

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 95412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 95412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1025 ms 105604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1028 ms 148624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 95412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 349 ms 117228 KB Output is correct
2 Correct 376 ms 118072 KB Output is correct
3 Correct 386 ms 118892 KB Output is correct
4 Correct 243 ms 114836 KB Output is correct
5 Correct 298 ms 117480 KB Output is correct
6 Correct 355 ms 119664 KB Output is correct
7 Correct 66 ms 96080 KB Output is correct
8 Correct 90 ms 95824 KB Output is correct
9 Correct 123 ms 99140 KB Output is correct
10 Correct 140 ms 112868 KB Output is correct
11 Correct 206 ms 118524 KB Output is correct
12 Correct 212 ms 118448 KB Output is correct

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 95412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 95412 KB Output isn't correct
2 Halted 0 ms 0 KB -