Submission #427936

#	Time	Username	Problem	Language	Result	Execution time	Memory
427936		BossBobster	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	563 ms	262148 KiB

apple

#include <iostream>
#include <string.h>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef pair<int, char> pic;
typedef pair<pii, int> piii;
typedef pair<double, double> pdd;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ull, ull> pull;
//#define max(n, m) ((n>m)?n:m)
//#define min(n, m) ((n<m)?n:m)
#define f first
#define s second
#define input() ios_base::sync_with_stdio(0);cin.tie(0);

struct node
{
    int l, r;
    node* left = nullptr;
    node* right = nullptr;
    int val;
    bool lazy;
    node(int l, int r, node* left, node* right, int val)
    {
        this->l = l; this->r = r; this->left = left; this->right = right; this->val = val;
    }
};

void update(node* cur, int lq, int rq)
{
    int mid = (cur->l + cur->r) / 2;
    if(cur->l != cur->r)
    {
        if(cur->left == nullptr)
            cur->left = new node(cur->l, mid, nullptr, nullptr, 0);
        if(cur->right == nullptr)
            cur->right = new node(mid+1, cur->r, nullptr, nullptr, 0);
    }
    if(cur->lazy)
    {
        cur->val = (cur->r - cur->l + 1);
        if(cur->l != cur->r)
        {
            cur->left->lazy = true;
            cur->right->lazy = true;
        }
        cur->lazy = false;
    }
    if(cur->l > rq || cur->r < lq || cur->l > cur->r) return;
    if(cur->l >= lq && cur->r <= rq)
    {
        cur->val = (cur->r - cur->l + 1);
        if(cur->l != cur->r)
        {
            cur->left->lazy = true;
            cur->right->lazy = true;
        }
        return;
    }
    update(cur->left, lq, rq); update(cur->right, lq, rq);
    cur->val = cur->left->val + cur->right->val;
}
int sum(node* cur, int lq, int rq)
{
    int mid = (cur->l + cur->r) / 2;
    if(cur->l != cur->r)
    {
        if(cur->left == nullptr)
            cur->left = new node(cur->l, mid, nullptr, nullptr, 0);
        if(cur->right == nullptr)
            cur->right = new node(mid+1, cur->r, nullptr, nullptr, 0);
    }
    if(cur->lazy)
    {
        cur->val = (cur->r - cur->l + 1);
        if(cur->l != cur->r)
        {
            cur->left->lazy = true;
            cur->right->lazy = true;
        }
        cur->lazy = false;
    }
    if(cur->l > rq || cur->r < lq || cur->l > cur->r) return 0;
    if(cur->l >= lq && cur->r <= rq)
        return cur->val;
    return sum(cur->left, lq, rq) + sum(cur->right, lq, rq);
}
int main()
{
    input();
    int m, type, a, b;
    int c = 0;
    cin >> m;
    node* root = new node(0, 1000000000, nullptr, nullptr, 0);
    while(m--)
    {
        cin >> type >> a >> b; a--; b--; a+=c; b+=c;
        if(type == 1)
        {
            c = sum(root, a, b);
            cout << c << "\n";
        }
        else
            update(root, a, b);
    }
}

• Subtask 1: 0 / 100