oj.uz

Submission #495372

# Submission time Handle Problem Language Result Execution time Memory
495372 2021-12-18T14:23:37 Z danikoynov Food Court (JOI21_foodcourt) C++14
21 / 100
 762 ms 17912 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;
const int maxn = 250010;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}



pair < ll, ll > lazy[4 * maxn];
ll tree[4 * maxn];

pair < ll, ll > merge_lazy(pair < ll, ll > p1, pair < ll, ll > p2)
{
    if (p1.second > p2.first)
    {
        return {p1.first, p1.second - p2.first + p2.second};
    }
    else
    {
        return {p1.first - p1.second + p2.first, p2.second};
    }
}
void push_lazy(int root, int left, int right)
{
    if (left == right)
    {
        tree[root] = max((ll)(0), tree[root] - lazy[root].first) + lazy[root].second;

    }
    else
    {
        lazy[root * 2] = merge_lazy(lazy[root * 2], lazy[root]);
        lazy[root * 2 + 1] = merge_lazy(lazy[root * 2 + 1], lazy[root]);
    }
    lazy[root] = {0, 0};
}

void range_update(int root, int left, int right, int qleft, int qright,
                  pair < ll, ll > val)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;
    if (left >= qleft && right <= qright)
    {
        lazy[root] = val;
        push_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    range_update(root * 2, left, mid, qleft, qright, val);
    range_update(root * 2 + 1, mid + 1, right, qleft, qright, val);
}

ll query(int root, int left, int right, int idx)
{
    ///cout << left << " - " << right << " " << lazy[root].first << " " << lazy[root].second << endl;
    push_lazy(root, left, right);
    if (left == right)
        return tree[root];

    int mid = (left + right) /2;
    if (idx <= mid)
        return query(root * 2, left, mid, idx);
    return query(root * 2 + 1, mid + 1, right, idx);
}
int n, m, q;
void solve()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= q; i ++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int l, r, c;
            ll k;
            cin >> l >> r >> c >> k;
            range_update(1, 1, n, l, r, {0, k});
        }
        else
        if (type == 2)
        {
            int l, r;
            ll k;
            cin >> l >> r >> k;
            range_update(1, 1, n, l, r, {k, 0});
        }
        else
        {
            int a;
            ll b;
            cin >> a >> b;
            ll val = query(1, 1, n, a);
            if (val >= b)
                cout << 1 << endl;
            else
                cout << 0 << endl;
        }

    }

}

int main()
{
    solve();
    return 0;
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 4284 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 705 ms 17272 KB Output is correct
2 Correct 536 ms 15944 KB Output is correct
3 Correct 649 ms 17632 KB Output is correct
4 Correct 549 ms 16048 KB Output is correct
5 Correct 543 ms 16112 KB Output is correct
6 Correct 760 ms 17860 KB Output is correct
7 Correct 305 ms 4604 KB Output is correct
8 Correct 379 ms 4552 KB Output is correct
9 Correct 762 ms 17896 KB Output is correct
10 Correct 730 ms 17904 KB Output is correct
11 Correct 681 ms 17880 KB Output is correct
12 Correct 705 ms 17764 KB Output is correct
13 Correct 660 ms 17760 KB Output is correct
14 Correct 642 ms 17716 KB Output is correct
15 Correct 656 ms 17780 KB Output is correct
16 Correct 678 ms 17692 KB Output is correct
17 Correct 692 ms 17664 KB Output is correct
18 Correct 709 ms 17908 KB Output is correct
19 Correct 666 ms 17708 KB Output is correct
20 Correct 736 ms 17632 KB Output is correct
21 Correct 656 ms 17912 KB Output is correct
22 Correct 696 ms 17812 KB Output is correct
23 Correct 661 ms 17596 KB Output is correct
24 Correct 673 ms 17712 KB Output is correct
25 Correct 573 ms 17352 KB Output is correct
26 Correct 685 ms 17452 KB Output is correct
27 Correct 533 ms 17524 KB Output is correct

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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