Submission #427936

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
427936	2021-06-15T05:26:45 Z	BossBobster	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	563 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->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.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	8556 KB	Output is correct
5	Correct	26 ms	10336 KB	Output is correct
6	Correct	27 ms	10008 KB	Output is correct
7	Correct	26 ms	10308 KB	Output is correct
8	Correct	217 ms	76996 KB	Output is correct
9	Correct	443 ms	130788 KB	Output is correct
10	Correct	490 ms	146852 KB	Output is correct
11	Correct	475 ms	159284 KB	Output is correct
12	Correct	503 ms	164808 KB	Output is correct
13	Correct	449 ms	205116 KB	Output is correct
14	Correct	463 ms	207036 KB	Output is correct
15	Runtime error	563 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-