oj.uz

답안 #985891

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
985891 2024-05-19T08:42:34 Z AlperenT_ 푸드 코트 (JOI21_foodcourt) C++17
21 / 100
 466 ms 72444 KB 
#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.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 405 ms 69448 KB Output is correct
2 Correct 292 ms 65620 KB Output is correct
3 Correct 431 ms 71284 KB Output is correct
4 Correct 297 ms 65936 KB Output is correct
5 Correct 292 ms 66128 KB Output is correct
6 Correct 393 ms 72036 KB Output is correct
7 Correct 165 ms 64444 KB Output is correct
8 Correct 178 ms 64500 KB Output is correct
9 Correct 385 ms 70236 KB Output is correct
10 Correct 372 ms 70468 KB Output is correct
11 Correct 378 ms 70992 KB Output is correct
12 Correct 394 ms 71792 KB Output is correct
13 Correct 407 ms 71140 KB Output is correct
14 Correct 393 ms 71804 KB Output is correct
15 Correct 395 ms 71732 KB Output is correct
16 Correct 466 ms 71736 KB Output is correct
17 Correct 402 ms 71720 KB Output is correct
18 Correct 435 ms 71456 KB Output is correct
19 Correct 429 ms 71708 KB Output is correct
20 Correct 423 ms 71328 KB Output is correct
21 Correct 401 ms 71764 KB Output is correct
22 Correct 439 ms 71764 KB Output is correct
23 Correct 443 ms 71752 KB Output is correct
24 Correct 405 ms 71764 KB Output is correct
25 Correct 328 ms 70260 KB Output is correct
26 Correct 316 ms 70740 KB Output is correct
27 Correct 310 ms 72444 KB Output is correct

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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