Submission #536848

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
536848	2022-03-14T05:59:16 Z	BossBobster	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	599 ms	262144 KB

apple

#include <iostream>
#include <string.h>
#include <random>
#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 <complex>
#include <valarray>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef pair<int, short> pish;
typedef pair<string, string> pss;
typedef pair<int, char> pic;
typedef pair<pii, int> piii;
typedef pair<double, double> pdd;
typedef pair<float, float> pff;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> plll;
typedef pair<pll, ld> plld;
typedef pair<int, ll> pil;
typedef pair<ull, ull> pull;
typedef pair<ld, ld> pld;
typedef complex<double> cd;
//#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);cout.tie(0);
#define eps 1e-9
//#define cin fin

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	14 ms	5844 KB	Output is correct
5	Correct	19 ms	7000 KB	Output is correct
6	Correct	17 ms	6772 KB	Output is correct
7	Correct	18 ms	7016 KB	Output is correct
8	Correct	160 ms	51444 KB	Output is correct
9	Correct	356 ms	87396 KB	Output is correct
10	Correct	328 ms	98056 KB	Output is correct
11	Correct	339 ms	106428 KB	Output is correct
12	Correct	345 ms	110248 KB	Output is correct
13	Correct	312 ms	136992 KB	Output is correct
14	Correct	300 ms	138328 KB	Output is correct
15	Correct	599 ms	254512 KB	Output is correct
16	Correct	584 ms	256640 KB	Output is correct
17	Correct	358 ms	145260 KB	Output is correct
18	Correct	329 ms	145328 KB	Output is correct
19	Correct	566 ms	262144 KB	Output is correct
20	Correct	563 ms	262144 KB	Output is correct