oj.uz

Submission #399475

# Submission time Handle Problem Language Result Execution time Memory
399475 2021-05-05T21:25:05 Z 534351 Food Court (JOI21_foodcourt) C++17
0 / 100
 1000 ms 18632 KB 
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

const int MAXN = 250013;

#define int long long

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

//a lazy can either say:
//1) increase everything by a value
//2) set everything to a value

int N, M, Q;
ll segmin[3 * MAXN], segmax[3 * MAXN];
pair<bool, ll> lazy[3 * MAXN]; //we need to store min?

void push(int w, int L, int R)
{
    if (lazy[w] == MP(false, 0ll)) return;
    if (lazy[w].fi) //set everything to this value.
    {
        ll v = lazy[w].se;
        segmin[w] = v;
        segmax[w] = v;
        if (L != R)
        {
            lazy[w << 1] = lazy[w];
            lazy[w << 1 | 1] = lazy[w];
        }
    }
    else //increase everything by a value.
    {
        ll v = lazy[w].se;
        segmin[w] += v;
        segmax[w] += v;
        if (L != R)
        {
            lazy[w << 1].se += lazy[w].se;
            lazy[w << 1 | 1].se += lazy[w].se;
        }
    }
    lazy[w] = {false, 0};
    return;
}
void update(int w, int L, int R, int a, int b, ll v)
{
    push(w, L, R);
    if (b < L || R < a)
    {
        return;
    }
    if (a <= L && R <= b)
    {
        if (segmin[w] + v >= 0 && segmax[w] + v >= 0)
        {
            lazy[w].se += v;
            push(w, L, R);
            return;
        }
        else if (segmin[w] + v <= 0 && segmax[w] + v <= 0)
        {
            lazy[w] = {true, 0};
            push(w, L, R);
            return;
        }
    }
    int mid = (L + R) >> 1;
    update(w << 1, L, mid, a, b, v);
    update(w << 1 | 1, mid + 1, R, a, b, v);
    segmin[w] = min(segmin[w << 1], segmin[w << 1 | 1]);
    segmax[w] = max(segmax[w << 1], segmax[w << 1 | 1]);
}
ll query(int w, int L, int R, int a)
{
    push(w, L, R);
    if (L == R)
    {
        return segmin[w];
    }
    int mid = (L + R) >> 1;
    if (a <= mid) return query(w << 1, L, mid, a);
    else return query(w << 1 | 1, mid + 1, R, a);
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    cin >> N >> M >> Q;
    while(Q--)
    {
        int qid;
        cin >> qid;
        if (qid == 1)
        {
            //join.
            int l, r, c; ll k;
            cin >> l >> r >> c >> k; l--; r--;
            update(1, 0, N - 1, l, r, k);
        }
        if (qid == 2)
        {
            int l, r; ll k;
            cin >> l >> r >> k; l--; r--;
            update(1, 0, N - 1, l, r, -k);
        }
        if (qid == 3)
        {
            int a; ll b;
            cin >> a >> b; a--;
            ll c = query(1, 0, N - 1, a);
            cout << ((c >= b) ? 1 : 0) << '\n';
        }
    }
    return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 460 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 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 18524 KB Output is correct
2 Correct 381 ms 18524 KB Output is correct
3 Correct 519 ms 18500 KB Output is correct
4 Correct 336 ms 18376 KB Output is correct
5 Correct 325 ms 18460 KB Output is correct
6 Correct 458 ms 18520 KB Output is correct
7 Correct 89 ms 2116 KB Output is correct
8 Correct 93 ms 2080 KB Output is correct
9 Correct 408 ms 18632 KB Output is correct
10 Correct 383 ms 18620 KB Output is correct
11 Correct 497 ms 18596 KB Output is correct
12 Correct 493 ms 18528 KB Output is correct
13 Correct 457 ms 18500 KB Output is correct
14 Correct 478 ms 18492 KB Output is correct
15 Correct 513 ms 18620 KB Output is correct
16 Correct 525 ms 18424 KB Output is correct
17 Correct 555 ms 18476 KB Output is correct
18 Correct 482 ms 18516 KB Output is correct
19 Correct 496 ms 18412 KB Output is correct
20 Correct 492 ms 18448 KB Output is correct
21 Correct 547 ms 18628 KB Output is correct
22 Correct 548 ms 18448 KB Output is correct
23 Correct 494 ms 18444 KB Output is correct
24 Correct 490 ms 18500 KB Output is correct
25 Correct 327 ms 18468 KB Output is correct
26 Correct 350 ms 18508 KB Output is correct
27 Execution timed out 1077 ms 18408 KB Time limit exceeded

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 5852 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 460 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 460 KB Output isn't correct
2 Halted 0 ms 0 KB -