oj.uz

답안 #905262

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
905262 2024-01-12T21:40:30 Z alexander707070 푸드 코트 (JOI21_foodcourt) C++14
13 / 100
 1000 ms 149008 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){

        maxsz[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);
            update(1,1,n,l,r,{s,i,t});
        }else if(type==2){
            cin>>l>>r>>s;
            rem(1,1,n,l,r,s);
        }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:175:31: warning: narrowing conversion of 's' from 'long long int' to 'int' [-Wnarrowing]
  175 |             update(1,1,n,l,r,{s,i,t});
      |                               ^

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 341 ms 116932 KB Output is correct
2 Correct 342 ms 118108 KB Output is correct
3 Correct 364 ms 118728 KB Output is correct
4 Correct 251 ms 114864 KB Output is correct
5 Correct 315 ms 117316 KB Output is correct
6 Correct 356 ms 119720 KB Output is correct
7 Correct 72 ms 96080 KB Output is correct
8 Correct 79 ms 95936 KB Output is correct
9 Correct 118 ms 99208 KB Output is correct
10 Correct 158 ms 112876 KB Output is correct
11 Correct 214 ms 118588 KB Output is correct
12 Correct 183 ms 118520 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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