Submission #873750

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
873750	2023-11-15T15:31:13 Z	Cristian	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	361 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
{
    ll 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	596 KB	Output is correct
4	Correct	16 ms	8628 KB	Output is correct
5	Correct	17 ms	10588 KB	Output is correct
6	Correct	17 ms	10076 KB	Output is correct
7	Correct	16 ms	10584 KB	Output is correct
8	Correct	143 ms	77788 KB	Output is correct
9	Correct	303 ms	132600 KB	Output is correct
10	Correct	337 ms	149076 KB	Output is correct
11	Correct	325 ms	161272 KB	Output is correct
12	Correct	361 ms	166744 KB	Output is correct
13	Correct	315 ms	207192 KB	Output is correct
14	Correct	320 ms	209232 KB	Output is correct
15	Runtime error	350 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-