Submission #985894

#	Time	Username	Problem	Language	Result	Execution time	Memory
985894		AlperenT_	Food Court (JOI21_foodcourt)	C++17	100 / 100	672 ms	93940 KiB

foodcourt

#include <bits/stdc++.h>
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
const int maxn = 3e5 + 10  , N = 1e5 +1 , lg = 20 , maxq = 202   , inf = 1e9  , maxk = 2022  , mod =998244353;
int n , q  , m , ds[maxn] , ans[maxn ] , ty[maxn];
struct n1{
    int mn , lz ,id = 0;
    n1(){
        mn =0 , lz =0 ; 
    }
};
n1 s1[4*maxn] ;
n1 operator+(n1 a , n1 b){
    n1 r ;
    r.mn = min(a.mn , b.mn);
    r.lz =0 ;
    if(a.mn == r.mn)r.id = a.id ;
    if(b.mn == r.mn)r.id = b.id;
    return r ;
}
void sh1(int p){
    int pl = p<<1,pr=p<<1|1;
    s1[pl].lz += s1[p].lz ;
    s1[pr].lz += s1[p].lz ;
    s1[pl].mn += s1[p].lz ;
    s1[pr].mn += s1[p].lz ;
    s1[p].lz =0 ;
}
void bui(int p = 1 , int l = 0 , int r = q){
    int pl = p<<1 ,pr=p<<1|1  ,mid=(l+r)/2 ;
    if(l == r){
        s1[p].id = l ;
        s1[p].mn = 0;
        return ;
    }
    bui(pl,l,mid);bui(pr,mid+1,r);
    s1[p] = s1[pl] + s1[pr];
}
void upd(int le, int ri ,int x , int p =1 , int l = 0 , int r =q){
    int pl = p<<1 ,pr=p<<1|1  ,mid=(l+r)/2 ;
    if(le > r|| l > ri)return ;
    if(l!=r)sh1(p);
    if(le <= l && r <= ri){
        s1[p].lz += x;
        s1[p].mn += x; 
        return ;
    }    
    upd(le,ri,x,pl,l,mid);
    upd(le,ri,x,pr,mid+1,r);
    s1[p]= s1[pl] + s1[pr]; 
}
n1 que(int le, int ri , int p= 1 ,int l =0 , int r = q){
    int mid = (l+r)/2 , pl=p<<1,pr=p<<1|1;
    if(le <= l && r <= ri)return s1[p];
    sh1(p);
    if(mid >= ri)return que(le,ri,pl,l,mid);
    if(mid < le)return que(le,ri,pr,mid+1,r);
    return que(le,ri,pl,l,mid) + que(le,ri,pr,mid+1,r) ;
}
 
struct n2{
    int a  , b ;
    n2(){
        a = b =0  ;
    }
};
n2 s2[4*maxn] ;

n2 operator+(n2 a, n2 b){
    n2 r ;
    r.a = a.a + b.a ;
    r.b = a.b + b.b;
    return r; 
}
void upd2(int x , int w, int p = 1, int l = 0 , int r = q){
    int mid = (l+r)/2 ,pl=p<<1,pr=p<<1|1;
    if(l == r){
        if(ty[l] == 1){
            s2[p].a += w;
        }else{
            s2[p].b +=w ;
        }
        return ;
    }
    if(mid < x)upd2(x,w,pr,mid+1,r);
    else upd2(x,w,pl,l,mid);
    s2[p] = s2[pl] + s2[pr] ;
}
n2 que2(int le ,int ri , int p= 1 ,int l =0 , int r = q){
    int mid = (l+r)/2 ,pl=p<<1,pr=p<<1|1;
    if(le <= l && r <= ri)return s2[p];
    if(ri <= mid)return que2(le,ri,pl,l,mid);
    if(le > mid)return que2(le,ri,pr,mid+1,r);
    return que2(le,ri,pl,l,mid) + que2(le,ri,pr,mid+1,r);
}
int w =0 , as =0;
void find(int x ,int p = 1 ,int l =0 , int r = q){
    if(r < x)return ; 
    int pl =p <<1, pr=p<<1|1, mid=(l+r)/2 ;
    if(l < x){
        find(x,pl,l,mid);
        if(as == -1)find(x,pr,mid+1,r) ;
        return ;
    }
    if(l >= x){
        if(w >= s2[p].a){
            w-=s2[p].a;
            return ;
        }
        if(l == r){
            as = l;
            return ;
        }
        find(x,pl,l,mid);
        if(as!=-1)return ;
        find(x,pr,mid+1,r);
    }
}

vector <pii> q1[maxn] ;
vector <pii> v1[maxn] , v2[maxn] ;
 
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m >> q ;
    rep(i , 1 , q){
        int t ;
        cin >> t ;
        ty[i] = t ;
        if(t == 3){
            int a, b ;
            cin >> a >> b;
            q1[a].pb({i , b}) ;
        }
        if(t==2){
            int l ,r , k ;
            cin >> l >> r >> k ;
            v2[l].pb({i , k});
            v1[r+1].pb({i , k}) ;
        }
        if(t==1){
            int l ,r , k , c;
            cin >> l >> r >> c >> k ;
            ds[i] = c; 
            v1[l].pb({i , k});
            v2[r+1].pb({i , k}) ;
        }
        ans[i] = -1 ;
    }
    bui() ;
    rep(t ,1 ,n){
        for(auto [i , k] : v2[t]){
            upd(i, q ,  -k) ;upd2(i , -k); 
        }
        for(auto [i , k] : v1[t]){
            upd(i , q , k) ;upd2(i , k);
        }
        for(auto [i , k] : q1[t]){
            upd(i , i , -(k-1));upd2(i , -(k-1)) ;
            int l = que(0 , i).id ;
            if(l == i){
                ans[i] =0 ;
            }else{
                w = -que2(l+1 , i).b;as =-1 ;
                find(l+1);
                ans[i] = ds[as] ;
            }
            upd(i , i , +(k-1)) ;upd2(i , k-1);
        }
    }
    rep(i ,1 ,q){
        if(ans[i] == -1)continue ;
        cout << ans[i] << "\n"  ;
    }
    cout << "\n";
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11