Submission #774433

#	Time	Username	Problem	Language	Result	Execution time	Memory
774433		VMaksimoski008	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1 ms	212 KiB

apple

#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define pii pair<int, int>
#define pll pair<long long, long long>
#define debug(x) cout << #x << " = " << x << endl
#define pb push_back
#define eb emplace_back
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int mod = 1e9 + 7;
using namespace std;

void setIO() {
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
}

struct node 
{
    ll sum, lazy;
    node *leftchild, *rightchild;
 
    node()
    {
        sum=0;
        lazy=0;
        leftchild=rightchild=nullptr;
    }
 
    ~node()
    {
        delete leftchild;
        delete rightchild;
    }
};
node *root=new node();
 
void extend(node *root, ll l, ll r)
{
    if (l!=r)
    {
        if (root->leftchild==nullptr) root->leftchild=new node();
        if (root->rightchild==nullptr) root->rightchild=new node();
    }
}
 
void down(node *root, ll l, ll r)
{
    if (root->lazy!=0)
    {
        root->sum=(r-l+1)*root->lazy;
        if (l!=r)
        {
            extend(root, l, r);
            root->leftchild->lazy=root->lazy;
            root->rightchild->lazy=root->lazy;
        }   
        root->lazy=0;
    }
}
 
void update(node *root, ll l, ll r, ll u, ll v, ll val)
{
    down(root, l, r);
    if (l>v || r<u || u>v) return;   
    if (u<=l && r<=v) 
    {
        root->lazy=val;
        down(root, l, r);   
        return;
    }
    extend(root, l, r);
    ll mid=(l+r)/2;
    update(root->leftchild, l, mid, u, v, val);
    update(root->rightchild, mid+1, r, u, v, val);
    root->sum = root->leftchild->sum + root->rightchild->sum;  
}
 
ll query(node *root, ll l, ll r, ll u, ll v)
{
    down(root, l, r);
    if (l>v || r<u || u>v) return 0;
    if (u<=l && r<=v) return root->sum;
    extend(root, l, r);
    ll mid=(l+r)/2;
    return query(root->leftchild, l, mid, u, v) + query(root->rightchild, mid+1, r, u, v);
}

int main() {
    setIO();

    int q;
    cin >> q;

    ll c = 0;
    while(q--) {
        int t, a, b;
        cin >> t >> a >> b;

        if(t == 1) {
            ll res = query(root, 1, 1e9, a+c, b+c);
            cout << res << '\n';
            c += res;
        } else {
            update(root, 1, 1e9, a+c, b+c, 1);
        }
    }

    return 0;
}

• Subtask 1: 0 / 100