Submission #536845

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
536845	2022-03-14T05:53:39 Z	BossBobster	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	397 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
{
    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->lazy)
    {
        cur->val = (cur->r - cur->l + 1);
        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);
            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)
        {
            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);
            cur->left->lazy = true;
            cur->right->lazy = true;
        }
        return;
    }
    if(cur->left == nullptr)
        cur->left = new node(cur->l, mid, nullptr, nullptr, 0);
    update(cur->left, lq, rq);
    if(cur->right == nullptr)
        cur->right = new node(mid+1, cur->r, nullptr, nullptr, 0);
    update(cur->right, 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 lq, int rq)
{
    int mid = (cur->l + cur->r) / 2;
    if(cur->lazy)
    {
        cur->val = (cur->r - cur->l + 1);
        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);
            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;
    int num = 0;
    if(cur->left != nullptr) num += sum(cur->left, lq, rq);
    if(cur->right != nullptr) num += sum(cur->right, lq, rq);
    return num;
}
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.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	16 ms	8508 KB	Output is correct
5	Correct	20 ms	10324 KB	Output is correct
6	Correct	20 ms	9928 KB	Output is correct
7	Correct	21 ms	10324 KB	Output is correct
8	Correct	200 ms	77004 KB	Output is correct
9	Correct	366 ms	130908 KB	Output is correct
10	Correct	367 ms	146776 KB	Output is correct
11	Correct	391 ms	159352 KB	Output is correct
12	Correct	380 ms	164880 KB	Output is correct
13	Correct	350 ms	205144 KB	Output is correct
14	Correct	352 ms	206968 KB	Output is correct
15	Runtime error	397 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-