Submission #873751

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
873751	2023-11-15T15:32:18 Z	Cristian	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	458 ms	262144 KB

apple

#include <iostream>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

using ll = long long;
//#define int ll
using pi = pair<int,int>;
using pll = pair<ll, ll>;

#define pb push_back
#define x first
#define y second

const int MOD = 1e9+7, INF = 1e9, NMAX = 2e5+1;
struct Node
{
    int sum, lazy;
    Node *l, *r;
    Node(ll sum): sum(sum), lazy(0), l(nullptr), r(nullptr){}
};
Node *tree = new Node(0);
void propagate(Node *k, int l, int r)
{
    if(k->lazy)
    {
        if(l != r)
        {
            if(k->l == nullptr)
                k->l = new Node(0);
            k->l->lazy = k->lazy;
            if(k->r == nullptr)
                k->r = new Node(0);
            k->r->lazy = k->lazy;
        }
        k->sum = r - l + 1;
        k->lazy = 0;
    }
}
void update(int i, int j, Node *k, int l = 1, int r = 1e9)
{
    propagate(k, l, r);
    if(l > r || r < i || j < l)
        return;
    if(i <= l && r <= j)
    {
        k->lazy = 1;
        propagate(k, l, r);
        return;
    }
    if(l <= (l + r) / 2)
    {
        if(k->l == nullptr)
            k->l = new Node(0);
        update(i, j, k->l, l, (l+r)/2);
    }
    if((l + r) / 2 + 1 <= r)
    {
        if(k->r == nullptr)
            k->r = new Node(0);
        update(i, j, k->r, (l+r)/2+1, r);
    }
    k->sum = 0;
    if(k->l != nullptr)
        k->sum += k->l->sum;
    if(k->r != nullptr)
        k->sum += k->r->sum;
}
ll query(int i, int j, Node *k, int l = 1, int r = 1e9)
{
    propagate(k, l, r);
    if(k == nullptr || l > r || r < i || j < l)
        return 0;
    if(i <= l && r <= j)
        return k->sum;
    ll sum = 0;
    if(k->l != nullptr && l <= (l+r)/2)
        sum += query(i, j, k->l, l, (l+r)/2);
    if(k->r != nullptr && (l+r)/2+1 <= r)
        sum += query(i, j, k->r, (l+r)/2+1, r);
    return sum;
}
void solve()
{
    ll n, i, op, l, r, ans, c = 0;
    cin >> n;
    for(i = 1; i <= n; i++)
    {
        cin >> op >> l >> r;
        if(op == 2)
            update(l + c, r + c, tree);
        else
        {
            ans = query(l + c, r + c, tree);
            cout << ans << '\n';
            c = ans;
        }
    }
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int T;
    T = 1;
    while(T--)
        solve();
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	13 ms	5936 KB	Output is correct
5	Correct	15 ms	7004 KB	Output is correct
6	Correct	15 ms	6932 KB	Output is correct
7	Correct	17 ms	7112 KB	Output is correct
8	Correct	145 ms	51564 KB	Output is correct
9	Correct	258 ms	87608 KB	Output is correct
10	Correct	260 ms	98132 KB	Output is correct
11	Correct	279 ms	106580 KB	Output is correct
12	Correct	283 ms	110164 KB	Output is correct
13	Correct	261 ms	137044 KB	Output is correct
14	Correct	286 ms	138576 KB	Output is correct
15	Correct	437 ms	254644 KB	Output is correct
16	Correct	458 ms	256512 KB	Output is correct
17	Correct	270 ms	145376 KB	Output is correct
18	Correct	278 ms	145748 KB	Output is correct
19	Correct	456 ms	262144 KB	Output is correct
20	Correct	456 ms	262144 KB	Output is correct