oj.uz

답안 #827700

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
827700 2023-08-16T16:34:14 Z ttamx 푸드 코트 (JOI21_foodcourt) C++14
0 / 100
 69 ms 28156 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=250005;
const int K=1<<19;
const ll inf=1e18;

int n,m,q;
int c[N],k[N],b[N];
vector<int> qr1[N],qr2[N],qr3[N];
ll sum=0;
int ans[N];

struct minsegtree{
    ll t[K],lz[K];
    void pushlz(int l,int r,int i){
        t[i]+=lz[i];
        if(l<r){
            lz[i*2]+=lz[i];
            lz[i*2+1]+=lz[i];
        }
        lz[i]=0;
    }
    void update(int l,int r,int i,int x,int y,ll v){
        pushlz(l,r,i);
        if(y<l||r<x)return;
        if(x<=l&&r<=y)return lz[i]+=v,pushlz(l,r,i),void();
        int m=(l+r)/2;
        update(l,m,i*2,x,y,v);
        update(m+1,r,i*2+1,x,y,v);
        t[i]=min(t[i*2],t[i*2+1]);
    }
    void update(int x,int y,ll v){
        update(1,q,1,x,y,v);
    }
    ll query(int l,int r,int i,int x,int y){
        pushlz(l,r,i);
        if(y<l||r<x)return inf;
        if(x<=l&&r<=y)return t[i];
        int m=(l+r)/2;
        return min(query(l,m,i*2,x,y),query(m+1,r,i*2+1,x,y));
    }
    ll query(int x,int y){
        return query(1,q,1,x,y);
    }
}s;

struct sumsegtree{
    ll t[K];
    void update(int l,int r,int i,int x,ll v){
        if(x<l||r<x)return;
        if(l==r)return void(t[i]+=v);
        int m=(l+r)/2;
        update(l,m,i*2,x,v);
        update(m+1,r,i*2+1,x,v);
        t[i]=t[i*2]+t[i*2+1];
    }
    void update(int x,ll v){
        update(1,q,1,x,v);
    }
    int query(int l,int r,int i,ll v){
        if(l==r)return t[i]>=v?l:0;
        int m=(l+r)/2;
        if(t[i*2]>=v)return query(l,m,i*2,v);
        return query(m+1,r,i*2+1,v-t[i*2]);
    }
    int query(ll v){
        return query(1,q,1,v);
    }
}ord;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> q;
    for(int i=1;i<=q;i++){
        int t;
        cin >> t;
        if(t==1){
            int l,r;
            cin >> l >> r >> c[i] >> k[i];
            qr1[l].emplace_back(i);
            qr1[r+1].emplace_back(-i);
        }else if(t==2){
            int l,r;
            cin >> l >> r >> k[i];
            qr2[l].emplace_back(i);
            qr2[r+1].emplace_back(-i);
        }else{
            int a;
            cin >> a >> b[i];
            qr3[a].emplace_back(i);
        }
    }
    for(int i=1;i<=n;i++){
        for(auto j:qr1[i]){
            if(j>0){
                s.update(j,q,k[j]);
                ord.update(j,k[j]);
            }else{
                j=-j;
                s.update(j,q,-k[j]);
                ord.update(j,-k[j]);
            }
        }
        for(auto j:qr2[i]){
            if(j>0){
                s.update(j,q,-k[j]);
                sum+=k[j];
            }else{
                j=-j;
                s.update(j,q,k[j]);
                sum-=k[j];
            }
        }
        for(auto j:qr3[i]){
            ll val=sum+min(0ll,s.query(1,j))+b[j];
            ans[j]=c[ord.query(val)];
        }
    }
    for(int i=1;i<=q;i++)if(b[i])cout << ans[i] << "\n";
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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