oj.uz

Submission #381292

# Submission time Handle Problem Language Result Execution time Memory
381292 2021-03-25T02:25:20 Z LittleCube Monkey and Apple-trees (IZhO12_apple) C++14
100 / 100
 207 ms 75628 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#pragma pack(0)
#define int long long
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
#define pb(x) emplace_back(x)
#define MOD 1000000007
#define MOD2 998244353
#define _INFINITY 9223372036854775807
#define fast ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int q, seg[6000000], _left[6000000], _right[6000000], pointer = 1, lazy[60000000], c, d, x, y;

int getval(int l, int r, int i)
{
    return max(seg[i], lazy[i] * (r - l + 1));
}

void modify(int l, int r, int i, int a, int b, int v)
{

    if (b < l || r < a)
        return;
    if ((a <= l && r <= b) || lazy[i])
        lazy[i] = v;
    else
    {
        int mid = (l + r) / 2;
        if (_left[i] == 0)
            _left[i] = ++pointer;
        if (_right[i] == 0)
            _right[i] = ++pointer;

        modify(l, mid, _left[i], a, b, v);
        modify(mid + 1, r, _right[i], a, b, v);

        seg[i] = getval(l, mid, _left[i]) + getval(mid + 1, r, _right[i]);
        //cout << "Pull " << i << "  left=" << seg[_left[i]] << " " << lazy[_left[i]] << " right=" << getval(mid + 1, r, _right[i]) << '\n';
    }
    //cout << "Block " << l << "->" << r << " Seg=" << seg[i] << " Lazy=" << lazy[i] << '\n';
}

int query(int l, int r, int i, int a, int b)
{
    //cout << "Block " << l << "->" << r << " Seg=" << seg[i] << " Lazy=" << lazy[i] << '\n';
    if (b < l || r < a)
        return 0;
    if (a <= l && r <= b)
        return getval(l, r, i);
    else
    {
        int mid = (l + r) / 2;
        if (_left[i] == 0)
            _left[i] = ++pointer;
        lazy[_left[i]] = max(lazy[_left[i]], lazy[i]);

        if (_right[i] == 0)
            _right[i] = ++pointer;
        lazy[_right[i]] = max(lazy[_right[i]], lazy[i]);

        lazy[i] = 0;
        seg[i] = getval(l, mid, _left[i]) + getval(mid + 1, r, _right[i]);
        return query(l, mid, _left[i], a, b) + query(mid + 1, r, _right[i], a, b);
    }
}

signed main()
{
    fast;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        cin >> d >> x >> y;
        if (d == 1)
        {
            int res = query(1, 2000000000, 1, x + c, y + c);
            c = res;
            cout << res << '\n';
        }
        else
            modify(1, 2000000000, 1, x + c, y + c, 1);
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 10 ms 2156 KB Output is correct
5 Correct 12 ms 2668 KB Output is correct
6 Correct 12 ms 2540 KB Output is correct
7 Correct 12 ms 2540 KB Output is correct
8 Correct 74 ms 18028 KB Output is correct
9 Correct 152 ms 31468 KB Output is correct
10 Correct 173 ms 34156 KB Output is correct
11 Correct 158 ms 36340 KB Output is correct
12 Correct 168 ms 37356 KB Output is correct
13 Correct 152 ms 40044 KB Output is correct
14 Correct 151 ms 39916 KB Output is correct
15 Correct 199 ms 73324 KB Output is correct
16 Correct 207 ms 74092 KB Output is correct
17 Correct 149 ms 41068 KB Output is correct
18 Correct 154 ms 41196 KB Output is correct
19 Correct 201 ms 75628 KB Output is correct
20 Correct 202 ms 75628 KB Output is correct