Submission #427940

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
427940	2021-06-15T05:29:23 Z	BossBobster	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	529 ms	262148 KB

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->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);
    if(cur->right == nullptr)
        cur->right = new node(mid+1, cur->r, nullptr, nullptr, 0);
    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->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;
    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);
    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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	22 ms	8528 KB	Output is correct
5	Correct	26 ms	10304 KB	Output is correct
6	Correct	26 ms	9924 KB	Output is correct
7	Correct	25 ms	10352 KB	Output is correct
8	Correct	203 ms	76936 KB	Output is correct
9	Correct	494 ms	130788 KB	Output is correct
10	Correct	462 ms	146756 KB	Output is correct
11	Correct	529 ms	159336 KB	Output is correct
12	Correct	496 ms	164844 KB	Output is correct
13	Correct	447 ms	205180 KB	Output is correct
14	Correct	520 ms	207064 KB	Output is correct
15	Runtime error	503 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-