oj.uz

답안 #547088

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
547088 2022-04-09T13:54:17 Z leaked 푸드 코트 (JOI21_foodcourt) C++14
13 / 100
 498 ms 78976 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_prep ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//#define int long long
//#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
const int N=3e5+1;
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
 struct node{
    ll s,s1,s2;
    ll mnpref;
    ll mxpref;
    node(){
        s=0,s1=0,s2=0;
        mnpref=mxpref=0;
    }
};
node mg(node a,node b){
    node c;
    c.s=a.s+b.s;
    c.s1=a.s1+b.s1;
    c.s2=a.s2+b.s2;
    c.mnpref=min({a.mnpref,b.mnpref+max(0LL,a.s)});
    c.mxpref=max({a.mxpref,b.mxpref+a.s1});
    return c;
}
struct sega{
    node t[4*N];
    void upd(int i,ll x,int tp,int v,int tl,int tr){
        if(tl==tr){
            t[v].s+=tp*x;
            if(x<0) t[v].s2+=tp*-x;
            else t[v].s1+=tp*x;

            t[v].mnpref=t[v].s;
            t[v].mxpref=t[v].s1;
//            umax(t[v].mxpref,0LL);
//            umin(t[v].mnpref,0LL);
//            cout<<"E "<<tl<<' '<<tr<<' '<<t[v].s2<<' '<<t[v]endl;
            return;
        }
        int tm=(tl+tr)>>1;
        if(tm>=i)
            upd(i,x,tp,v<<1,tl,tm);
        else
            upd(i,x,tp,v<<1|1,tm+1,tr);
        t[v]=mg(t[2*v],t[2*v+1]);
    }
    int findj(ll x,int i,int v,int tl,int tr){
        umax(x,0LL);
        if(tl>i) return -1;
        if(tr<=i){
            if((x+t[v].mnpref)>=0)
                return -1;
        }
        if(tl==tr) return tl;

        int tm=(tl+tr)>>1;
        int j=findj(x+t[2*v].s,i,2*v+1,tm+1,tr);
        if(j==-1)
            return findj(x,i,2*v,tl,tm);
        return j;
    }
    int findj1(ll x,int i,ll wt,int v,int tl,int tr){
        if(tr<i)
            return -1;
//        cout<<"V "<<v<<' '<<tl<<' '<<tr<<' '<<t[v].s1<<' '<<t[v].mxpref<<endl;
        if(tl>=i){
            if((x+t[v].mxpref)<wt)
                return -1;
        }
        if(tl==tr) return tl;
        int tm=(tl+tr)>>1;

        int j=findj1(x,i,wt,2*v,tl,tm);
        if(j!=-1) return j;
        return findj1(x+t[2*v].s1,i,wt,2*v+1,tm+1,tr);
    }
    node emp;
    node gets(int l,int r,int v,int tl,int tr){
//        cout<<l<<' '<<r<<' '<<"TL "<<tl<<' '<<tr<<' '<<t[v].s<<endl;
        if(tl>=l&&tr<=r)
            return t[v];
        if(tl>r||tr<l)
            return emp;
        int tm=(tl+tr)>>1;
        return mg(gets(l,r,2*v,tl,tm),gets(l,r,2*v+1,tm+1,tr));
    }
}sega;
signed main(){
    fast_prep;
    int n,m,q;
    cin>>n>>m>>q;
    vec<int> t(q),l(q),r(q),c(q);
    vec<ll>k(q);
    vec<vec<int>> rs(n,vec<int>());
    vec<vec<int>> ls(n,vec<int>());
    vec<vec<int>> asks(n,vec<int>());
    vec<int>ans(q);
    for(int i=0;i<q;i++){
        cin>>t[i];
        if(t[i]==1){
            cin>>l[i]>>r[i]>>c[i]>>k[i];
            --l[i];--r[i];
            ls[l[i]].pb(i);
            rs[r[i]].pb(i);
//            sega.add(l[i],r[i],k[i],i,1,0,n-1);
        }
        else if(t[i]==2){
            cin>>l[i]>>r[i]>>k[i];
            --l[i];--r[i];
            ls[l[i]].pb(i);rs[r[i]].pb(i);
//            fen.add(l[i],r[i],k[i]);
//            sega.add(l[i],r[i],-k[i],i,1,0,n-1);
        }
        else{
            cin>>l[i]>>k[i];
            --l[i];
            asks[l[i]].pb(i);
        }
    }
    vec<int> ids(q);
    for(int i=0;i<n;i++){
        for(auto &j : ls[i]){
            if(t[j]==1) sega.upd(j,k[j],1,1,0,q-1);
            else sega.upd(j,-k[j],1,1,0,q-1);
        }
        for(auto &j : asks[i]){
            int f=sega.findj(0,j,1,0,q-1);
            ++f;
            node that=sega.gets(0,f-1,1,0,q-1);
            ll toadd=-that.s;
            ll need=sega.gets(0,j,1,0,q-1).s2+k[j];
            int s=sega.findj1(toadd,f,need,1,0,q-1);
            if(s==-1 || s>=j) ans[j]=0;
            else ans[j]=c[s];
        }
        for(auto &j : rs[i]){
            if(t[j]==1) sega.upd(j,k[j],-1,1,0,q-1);
            else sega.upd(j,-k[j],-1,1,0,q-1);
        }
    }
    for(int i=0;i<q;i++){
        if(t[i]==3) cout<<ans[i]<<'\n';
    }
    return 0;
}
/*
3 5 5
1 2 3 5 2
1 1 2 2 4
2 1 3 3
1 2 3 4 2
3 3 2

3 5 3
1 2 3 5 2
1 1 2 2 4
3 2 3

2 1 3 3
3 1 2
1 2 3 4 2

*/

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 56436 KB Output is correct
2 Correct 120 ms 56516 KB Output is correct
3 Correct 148 ms 56428 KB Output is correct
4 Correct 139 ms 56432 KB Output is correct
5 Correct 124 ms 56460 KB Output is correct
6 Correct 117 ms 56420 KB Output is correct
7 Correct 78 ms 49728 KB Output is correct
8 Correct 78 ms 49952 KB Output is correct
9 Correct 140 ms 56428 KB Output is correct
10 Correct 116 ms 56396 KB Output is correct
11 Correct 132 ms 56348 KB Output is correct
12 Correct 132 ms 56404 KB Output is correct
13 Incorrect 118 ms 54356 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 55784 KB Output is correct
2 Correct 141 ms 55432 KB Output is correct
3 Correct 112 ms 56256 KB Output is correct
4 Correct 84 ms 54708 KB Output is correct
5 Correct 98 ms 55644 KB Output is correct
6 Correct 134 ms 56200 KB Output is correct
7 Correct 74 ms 49612 KB Output is correct
8 Correct 66 ms 49532 KB Output is correct
9 Correct 92 ms 55116 KB Output is correct
10 Correct 86 ms 53692 KB Output is correct
11 Correct 110 ms 55244 KB Output is correct
12 Correct 115 ms 55280 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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