oj.uz

답안 #402045

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402045 2021-05-11T08:41:41 Z Jarif_Rahman 푸드 코트 (JOI21_foodcourt) C++17
21 / 100
 668 ms 31328 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e16+1;
struct segtree_beats{
    struct node{
        ll mn[2], cnt[2];
        ll sm, lazy_add;
        node(){
            mn[0] = 0, mn[1] = inf;
            cnt[0] = 1, cnt[1] = 0;
            sm = 0;
            lazy_add = 0;
        }
        node operator+(node a){
            node rt;
            if(mn[0] < a.mn[0]){
                rt.mn[0] = mn[0], rt.cnt[0] = cnt[0];
                if(mn[1] < a.mn[0]) rt.mn[1] = mn[1], rt.cnt[1] = cnt[1];
                else if(mn[1] > a.mn[0]) rt.mn[1] = a.mn[0], rt.cnt[1] = a.cnt[0];
                else rt.mn[1] = mn[1], rt.cnt[1] = cnt[1]+a.cnt[0];
            }
            else if(mn[0] > a.mn[0]){
                rt.mn[0] = a.mn[0], rt.cnt[0] = a.cnt[0];
                if(mn[0] < a.mn[1]) rt.mn[1] = mn[0], rt.cnt[1] = cnt[0];
                else if(mn[0] > a.mn[1]) rt.mn[1] = a.mn[1], rt.cnt[1] = a.cnt[1];
                else rt.mn[1] = mn[0], rt.cnt[1] = cnt[0]+a.cnt[1];
            }
            else{
                rt.mn[0] = mn[0], rt.cnt[0] = cnt[0]+a.cnt[0];
                if(mn[1] < a.mn[1]) rt.mn[1] = mn[1], rt.cnt[1] = cnt[1];
                else if(mn[1] > a.mn[1]) rt.mn[1] = a.mn[1], rt.cnt[1] = a.cnt[1];
                else rt.mn[1] = mn[1], rt.cnt[1] = cnt[1]+a.cnt[1];
            }
            rt.sm = sm+a.sm;
            return rt;
        }
        void propagate(node nd, int sz){
            lazy_add+=nd.lazy_add;
            sm+=nd.lazy_add*sz;
            mn[0]+=nd.lazy_add;
            if(mn[1] != inf) mn[1]+=nd.lazy_add;
            if(nd.mn[0] <= mn[0]) return;
            sm+=(nd.mn[0]-mn[0])*cnt[0];
            mn[0] = nd.mn[0];
        }
    };
    int k;
    vector<node> v;
    segtree_beats(int n){
        k = 1;
        while(k < n) k*=2;
        k*=2;
        v.resize(k, node());
        for(int i = k/2-1; i > 0; i--) v[i] = v[2*i]+v[2*i+1];
    }
    void add(int l, int r, int nd, int a, int b, ll x){
        if(a > r || b < l){
            return;
        }
        if(a >= l && b <= r){
            node nd0;
            nd0.lazy_add = x;
            nd0.mn[0] = -inf+1;
            v[nd].propagate(nd0, b-a+1);
            return;
        }
        int md = (a+b)/2;
        v[2*nd].propagate(v[nd], md-a+1);
        v[2*nd+1].propagate(v[nd], b-md);
        v[nd].lazy_add = 0;
        add(l, r, 2*nd, a, md, x);
        add(l, r, 2*nd+1, md+1, b, x);
        v[nd] = v[2*nd]+v[2*nd+1];
    }
    void add(int l, int r, ll x){
        add(l, r, 1, 0, k/2-1, x);
    }
    void chmx(int l, int r, int nd, int a, int b, ll x){
        if(a > r || b < l || v[nd].mn[0] >= x){
            return;
        }
        if(a >= l && b <= r && v[nd].mn[1] > x){
            node nd0;
            nd0.mn[0] = x;
            v[nd].propagate(nd0, b-a+1);
            return;
        }
        int md = (a+b)/2;
        v[2*nd].propagate(v[nd], md-a+1);
        v[2*nd+1].propagate(v[nd], b-md);
        v[nd].lazy_add = 0;
        chmx(l, r, 2*nd, a, md, x);
        chmx(l, r, 2*nd+1, md+1, b, x);
        v[nd] = v[2*nd]+v[2*nd+1];
    }
    void chmx(int l, int r, ll x){
        chmx(l, r, 1, 0, k/2-1, x);
    }
    ll sum(int l, int r, int nd, int a, int b){
        if(a > r || b < l){
            return 0;
        }
        if(a >= l && b <= r){
            return v[nd].sm;
        }
        int md = (a+b)/2;
        v[2*nd].propagate(v[nd], md-a+1);
        v[2*nd+1].propagate(v[nd], b-md);
        v[nd].lazy_add = 0;
        ll rt = sum(l, r, 2*nd, a, md) + sum(l, r, 2*nd+1, md+1, b);
        v[nd] = v[2*nd]+v[2*nd+1];
        return rt;
    }
    ll sum(int l, int r){
        return sum(l, r, 1, 0, k/2-1);
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, q; cin >> n >> m >> q;
    segtree_beats beats(n);
    while(q--){
        int tt; cin >> tt;
        if(tt == 1){
            int l, r, c; ll k; cin >> l >> r >> c >> k; l--, r--;
            beats.add(l, r, k);
        }
        else if(tt == 2){
            int l, r; ll k; cin >> l >> r >> k; l--, r--;
            beats.add(l, r, -k);
            beats.chmx(l, r, 0LL);
        }
        else{
            int a; ll b; cin >> a >> b; a--;
            cout << (beats.sum(a, a) >= b ? 1:0) << "\n";
        }
    }
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 555 ms 30436 KB Output is correct
2 Correct 526 ms 29252 KB Output is correct
3 Correct 579 ms 31072 KB Output is correct
4 Correct 385 ms 29380 KB Output is correct
5 Correct 397 ms 29668 KB Output is correct
6 Correct 530 ms 31216 KB Output is correct
7 Correct 101 ms 4532 KB Output is correct
8 Correct 107 ms 4532 KB Output is correct
9 Correct 481 ms 31236 KB Output is correct
10 Correct 471 ms 31180 KB Output is correct
11 Correct 544 ms 31172 KB Output is correct
12 Correct 533 ms 31172 KB Output is correct
13 Correct 552 ms 31084 KB Output is correct
14 Correct 586 ms 31128 KB Output is correct
15 Correct 645 ms 31328 KB Output is correct
16 Correct 634 ms 31044 KB Output is correct
17 Correct 668 ms 31020 KB Output is correct
18 Correct 616 ms 31136 KB Output is correct
19 Correct 608 ms 31260 KB Output is correct
20 Correct 624 ms 31180 KB Output is correct
21 Correct 649 ms 31152 KB Output is correct
22 Correct 607 ms 31064 KB Output is correct
23 Correct 613 ms 31044 KB Output is correct
24 Correct 616 ms 31044 KB Output is correct
25 Correct 425 ms 30580 KB Output is correct
26 Correct 439 ms 30796 KB Output is correct
27 Correct 519 ms 30976 KB Output is correct

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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