oj.uz

Submission #870485

# Submission time Handle Problem Language Result Execution time Memory
870485 2023-11-08T05:39:33 Z garam1732 Food Court (JOI21_foodcourt) C++14
21 / 100
 296 ms 39504 KB 
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define bl " "
#define endl "\n"
#define all(v) v.begin(), v.end()
#define comp(v) v.erase(unique(all(v)), v.end())
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 250250;
const int MOD = 998244353;

vector<pll> tree, lazy;

void prop(pll &x, pll &y) {
    x.ff += y.ff;
    x.ss = max(x.ss+y.ff, y.ss);
}

void update_lazy(int node, int s, int e) {
    if(lazy[node].ff || lazy[node].ss) {
        prop(tree[node], lazy[node]);

        if(s != e) {
            prop(lazy[node<<1], lazy[node]);
            prop(lazy[node<<1|1], lazy[node]);
        }

        lazy[node] = pll(0, 0);
    }
}

void update(int node, int s, int e, int l, int r, pll v) {
    update_lazy(node, s, e);
    if(e < l || r < s) return;
    if(l <= s && e <= r) {
        prop(lazy[node], v);
        update_lazy(node, s, e);
        return;
    }

    int mid = s+e>>1;
    update(node<<1, s, mid, l, r, v); update(node<<1|1, mid+1, e, l, r, v);
}

void solve(int node, int s, int e, int idx, ll &x) {
    update_lazy(node, s, e);
    if(e < idx || idx < s) return;
    if(s == e) {
        x = max(tree[node].ff, tree[node].ss);
        return;
    }

    int mid = s+e>>1;
    solve(node<<1, s, mid, idx, x); solve(node<<1|1, mid+1, e, idx, x);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int n, m, q; cin >> n >> m >> q;
    tree.resize(1 << 20); lazy.resize(1 << 20);

    while(q--) {
        int t; cin >> t;
        if(t == 1) {
            int l, r, c, k; cin >> l >> r >> c >> k;
            update(1, 1, n, l, r, pll(k, 0));
        }
        else if(t == 2) {
            int l, r, k; cin >> l >> r >> k;
            update(1, 1, n, l, r, pll(-k, 0));
        }
        else {
            int a; ll b; cin >> a >> b;
            ll x; solve(1, 1, n, a, x);
            //cout<<x<<endl;
            cout << (x >= b ? 1 : 0) << endl;
        }
    }
}

Compilation message

foodcourt.cpp: In function 'void update(int, int, int, int, int, pll)':
foodcourt.cpp:47:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     int mid = s+e>>1;
      |               ~^~
foodcourt.cpp: In function 'void solve(int, int, int, int, ll&)':
foodcourt.cpp:59:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int mid = s+e>>1;
      |               ~^~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 38792 KB Output is correct
2 Correct 177 ms 37460 KB Output is correct
3 Correct 257 ms 39252 KB Output is correct
4 Correct 202 ms 37712 KB Output is correct
5 Correct 190 ms 37704 KB Output is correct
6 Correct 267 ms 39504 KB Output is correct
7 Correct 63 ms 37524 KB Output is correct
8 Correct 65 ms 37460 KB Output is correct
9 Correct 234 ms 39480 KB Output is correct
10 Correct 245 ms 39504 KB Output is correct
11 Correct 254 ms 39504 KB Output is correct
12 Correct 259 ms 39504 KB Output is correct
13 Correct 265 ms 39440 KB Output is correct
14 Correct 265 ms 39256 KB Output is correct
15 Correct 265 ms 39292 KB Output is correct
16 Correct 262 ms 39252 KB Output is correct
17 Correct 269 ms 39172 KB Output is correct
18 Correct 274 ms 39420 KB Output is correct
19 Correct 255 ms 39312 KB Output is correct
20 Correct 279 ms 39400 KB Output is correct
21 Correct 258 ms 39252 KB Output is correct
22 Correct 258 ms 39408 KB Output is correct
23 Correct 296 ms 39416 KB Output is correct
24 Correct 263 ms 39296 KB Output is correct
25 Correct 210 ms 38872 KB Output is correct
26 Correct 227 ms 38996 KB Output is correct
27 Correct 183 ms 38992 KB Output is correct

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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