oj.uz

Submission #387218

# Submission time Handle Problem Language Result Execution time Memory
387218 2021-04-08T06:46:17 Z Jarif_Rahman Food Court (JOI21_foodcourt) C++17
0 / 100
 1000 ms 27372 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 = 1e18;
struct segtree{
    struct node{
        ll sm, lazy_assign, lazy_add, mx, mn;
        node(){
            sm = 0LL, mx = 0LL, mn = 0LL, lazy_assign = -inf, lazy_add = 0LL;
        }
        void calc(node a, node b){
            sm = a.sm+b.sm;
            mx = max(a.mx, b.mx);
            mn = min(a.mn, b.mn);
        }
    };
    int k;
    vector<node> v;
    segtree(int n){
        k = 1;
        while(k <= n) k*=2; k*=2;
        v.resize(k, node());
    }
    void chmx(int l, int r, int nd, int a, int b, ll x, ll ex, bool tt){
        if(a > r || b < l || (tt ? ex:v[nd].mn+ex) >= x){
            if(tt){
                v[nd].lazy_assign = ex;
                v[nd].lazy_add = 0LL;
                v[nd].sm = (b-a+1)*ex;
                v[nd].mn = ex;
                v[nd].mx = ex;
            }
            else{
                v[nd].lazy_add+=ex;
                v[nd].sm+=(b-a+1)*ex;
                v[nd].mn+=ex;
                v[nd].mx+=ex;
            }
            return;
        }
        if(a >= l && b <= r && (tt ? ex:v[nd].mx+ex) < x){
            v[nd].lazy_assign = x;
            v[nd].lazy_add = 0LL;
            v[nd].sm = (b-a+1)*x;
            v[nd].mn = x;
            v[nd].mx = x;
            return;
        }
        int md = (a+b)/2;
        if(!tt){
            ex+=v[nd].lazy_add;
            if(v[nd].lazy_assign != -inf){
                ex+=v[nd].lazy_assign;
                tt = 1;
            }
        }
        v[nd].lazy_add = 0LL;
        v[nd].lazy_assign = -inf;
        chmx(l, r, 2*nd, a, md, x, ex, tt);
        chmx(l, r, 2*nd+1, md+1, b, x, ex, tt);
        if(2*nd+1 < k) v[nd].calc(v[2*nd], v[2*nd+1]);
    }
    void chmx(int l, int r, ll x){
        chmx(l, r, 1, 0, k/2-1, x, 0LL, 0);
    }
    void add(int l, int r, int nd, int a, int b, ll x, ll ex, bool tt){
        if(a > r || b < l){
            if(tt){
                v[nd].lazy_assign = ex;
                v[nd].lazy_add = 0LL;
                v[nd].sm = (b-a+1)*ex;
                v[nd].mn = ex;
                v[nd].mx = ex;
            }
            else{
                v[nd].lazy_add+=ex;
                v[nd].sm+=(b-a+1)*ex;
                v[nd].mn+=ex;
                v[nd].mx+=ex;
            }
            return;
        }
        if(a >= l && b <= r){
            if(tt){
                v[nd].lazy_assign = ex;
                v[nd].lazy_add = 0LL;
                v[nd].sm = (b-a+1)*ex;
                v[nd].mn = ex;
                v[nd].mx = ex;
            }
            else{
                v[nd].lazy_add+=ex;
                v[nd].sm+=(b-a+1)*ex;
                v[nd].mn+=ex;
                v[nd].mx+=ex;
            }
            v[nd].lazy_add+=x;
            v[nd].sm+=(b-a+1)*x;
            v[nd].mn+=x;
            v[nd].mx+=x;
            return;
        }
        int md = (a+b)/2;
        if(!tt){
            ex+=v[nd].lazy_add;
            if(v[nd].lazy_assign != -inf){
                ex+=v[nd].lazy_assign;
                tt = 1;
            }
        }
        v[nd].lazy_add = 0LL;
        v[nd].lazy_assign = -inf;
        add(l, r, 2*nd, a, md, x, ex, tt);
        add(l, r, 2*nd+1, md+1, b, x, ex, tt);
        if(2*nd+1 < k) v[nd].calc(v[2*nd], v[2*nd+1]);
    }
    void add(int l, int r, ll x){
        add(l, r, 1, 0, k/2-1, x, 0LL, 0);
    }
    ll sum(int l, int r, int nd, int a, int b, ll ex, bool tt){
        if(a > r || b < l){
            if(tt){
                v[nd].lazy_assign = ex;
                v[nd].lazy_add = 0LL;
                v[nd].sm = (b-a+1)*ex;
                v[nd].mn = ex;
                v[nd].mx = ex;
            }
            else{
                v[nd].lazy_add+=ex;
                v[nd].sm+=(b-a+1)*ex;
                v[nd].mn+=ex;
                v[nd].mx+=ex;
            }
            return 0LL;
        }
        if(a >= l && b <= r){
            if(tt){
                v[nd].lazy_assign = ex;
                v[nd].lazy_add = 0LL;
                v[nd].sm = (b-a+1)*ex;
                v[nd].mn = ex;
                v[nd].mx = ex;
            }
            else{
                v[nd].lazy_add+=ex;
                v[nd].sm+=(b-a+1)*ex;
                v[nd].mn+=ex;
                v[nd].mx+=ex;
            }
            return v[nd].sm;
        }
        int md = (a+b)/2;
        if(!tt){
            ex+=v[nd].lazy_add;
            if(v[nd].lazy_assign != -inf){
                ex+=v[nd].lazy_assign;
                tt = 1;
            }
        }
        v[nd].lazy_add = 0LL;
        v[nd].lazy_assign = -inf;
        ll rt = sum(l, r, 2*nd, a, md, ex, tt) + sum(l, r, 2*nd+1, md+1, b, ex, tt);
        if(2*nd+1 < k) v[nd].calc(v[2*nd], v[2*nd+1]);
        return rt;
    }
    ll sum(int l, int r){
        return sum(l, r, 1, 0, k/2-1, 0LL, 0);
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, q; cin >> n >> m >> q;
    segtree seg(n);
    while(q--){
        int tt; cin >> tt;
        if(tt == 1){
            int l, r, c; ll k; cin >> l >> r >> c >> k; l--, r--;
            seg.add(l, r, k);
        }
        else if(tt == 2){
            int l, r; ll k; cin >> l >> r >> k; l--, r--;
            seg.add(l, r, -k);
            seg.chmx(0, seg.k/2-1, 0);
        }
        else{
            int a; ll b; cin >> a >> b; a--;
            cout << (seg.sum(a, a) >= b ? 1:0) << "\n";
        }
    }
}

Compilation message

foodcourt.cpp: In constructor 'segtree::segtree(int)':
foodcourt.cpp:25:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   25 |         while(k <= n) k*=2; k*=2;
      |         ^~~~~
foodcourt.cpp:25:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   25 |         while(k <= n) k*=2; k*=2;
      |                             ^

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 6536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 21996 KB Output is correct
2 Correct 373 ms 25196 KB Output is correct
3 Correct 478 ms 26948 KB Output is correct
4 Correct 331 ms 25428 KB Output is correct
5 Correct 324 ms 25472 KB Output is correct
6 Correct 453 ms 27372 KB Output is correct
7 Correct 94 ms 4588 KB Output is correct
8 Correct 108 ms 4688 KB Output is correct
9 Correct 432 ms 27276 KB Output is correct
10 Correct 415 ms 27116 KB Output is correct
11 Correct 482 ms 27092 KB Output is correct
12 Correct 470 ms 27116 KB Output is correct
13 Correct 463 ms 26988 KB Output is correct
14 Correct 494 ms 27076 KB Output is correct
15 Correct 528 ms 27116 KB Output is correct
16 Correct 508 ms 26932 KB Output is correct
17 Correct 505 ms 27244 KB Output is correct
18 Correct 496 ms 27372 KB Output is correct
19 Correct 480 ms 26988 KB Output is correct
20 Correct 488 ms 27116 KB Output is correct
21 Correct 506 ms 26988 KB Output is correct
22 Correct 563 ms 26988 KB Output is correct
23 Correct 489 ms 26988 KB Output is correct
24 Correct 504 ms 26988 KB Output is correct
25 Correct 371 ms 26604 KB Output is correct
26 Correct 360 ms 26804 KB Output is correct
27 Execution timed out 1080 ms 25324 KB Time limit exceeded

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 6508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -