Submission #985891

#	Time	Username	Problem	Language	Result	Execution time	Memory
985891		AlperenT_	Food Court (JOI21_foodcourt)	C++17	21 / 100	466 ms	72444 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 ];
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) ;
}



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 ;
        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) ;
        }
        for(auto [i , k] : v1[t]){
            upd(i , q , k) ;
        }
        for(auto [i , k] : q1[t]){
            upd(i , i , -(k-1));
            if(que(0 , i).id != i){
                ans[i] =1 ;
            }else{
                ans[i] =0 ;
            }
            upd(i , i , +(k-1)) ;
        }
    }
    rep(i ,1 ,q){
        if(ans[i] == -1)continue ;
        cout << ans[i] << "\n"  ;
    }
    cout << "\n";
}
/*
3 1 6
1 1 3 1 2 
2 2 2 4 
3 2 1 
3 1 1 
3 3 3
3 3 2

*/

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