Submission #427932

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
427932	2021-06-15T05:23:21 Z	BossBobster	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	510 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;
    ll val;
    bool lazy;
    node(int l, int r, node* left, node* right, ll 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;
}
ll 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;
    ll 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	28 ms	8588 KB	Output is correct
5	Correct	27 ms	10492 KB	Output is correct
6	Correct	32 ms	10144 KB	Output is correct
7	Correct	27 ms	10520 KB	Output is correct
8	Correct	233 ms	77832 KB	Output is correct
9	Correct	449 ms	132652 KB	Output is correct
10	Correct	467 ms	148656 KB	Output is correct
11	Correct	494 ms	161068 KB	Output is correct
12	Correct	510 ms	166732 KB	Output is correct
13	Correct	446 ms	207304 KB	Output is correct
14	Correct	486 ms	209092 KB	Output is correct
15	Runtime error	506 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-