Submission #895546

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
895546	2023-12-30T08:43:23 Z	abysmal	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	292 ms	136172 KB

apple

#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<iomanip>
#include<string>
#include<math.h>
#include<assert.h>

using namespace std;

const double PI = (double) atan(1.0) * 4;
const int64_t INF = (int64_t) 5e18 + 777;
const int64_t mINF = (int64_t) 1e6 + 777;
const int64_t offset = (int64_t) 1e6 + 777;
const int64_t MOD = 1e9 + 7;
const int nbit = 19;
const int ndig = 10;
const int nchar = 26;
const int p1 = 31;
const int p2 = 53;
const int D = 4;
int dr[D] = {0, 1, 0, -1};
int dc[D] = {1, 0, -1, 0};
// 0 right // 1 down // 2 left // 3 up

struct Node
{
    int sum; int tag;
    Node* left; Node* right;
    Node(int sum_ = 0, int tag_ = 0) : sum(sum_), tag(tag_)
    {
        left = NULL; right = NULL;
    }
};

struct Tree
{
    Node* root;
    Tree()
    {
        root = new Node();
    }

    void update(Node* cur, int nleft, int nright, int left, int right)
    {
        if(left > nright || nleft > right) return;
        int len = nright - nleft + 1;
        if(left <= nleft && nright <= right)
        {
            cur->tag++;
            cur->sum = len;

            return;
        }

        push(cur, len / 2);
        int mid = nleft + (nright - nleft) / 2;
        if(cur->left == NULL) cur->left = new Node();
        if(cur->right == NULL) cur->right = new Node();
        update(cur->left, nleft, mid, left, right);
        update(cur->right, mid + 1, nright, left, right);
        cur->sum = cur->left->sum + cur->right->sum;
    }

    int get(Node* cur, int nleft, int nright, int left, int right)
    {
        if(cur == NULL) return 0;
        if(left > nright || nleft > right) return 0;
        if(left <= nleft && nright <= right) return cur->sum;
        int len = nright - nleft + 1;
        push(cur, len / 2);
        int mid = nleft + (nright - nleft) / 2;
        return get(cur->left, nleft, mid, left, right) +
               get(cur->right, mid + 1, nright, left, right);
    }

    void updateRange(int l, int r)
    {
        update(root, 1, (1 << 30), l, r);
    }

    int query(int l, int r)
    {
        return get(root, 1, (1 << 30), l, r);
    }

    void push(Node* i, int len)
    {
        if(i->tag == 0) return;
        if(i->left == NULL) i->left = new Node();
        if(i->right == NULL) i->right = new Node();

        i->left->tag += i->tag;
        i->left->sum = len;

        i->right->tag += i->tag;
        i->right->sum = len;
        i->tag = 0;
    }
};

struct Solution
{
    Solution() {}

    void solve()
    {
        int n;
        cin >> n;

        int c = 0;
        Tree tree;
        for(int i = 0; i < n; i++)
        {
            int t; int x; int y;
            cin >> t >> x >> y;
            x += c; y += c;
            if(t == 1)
            {
                c = tree.query(x, y);
                cout << c << "\n";
            }
            else tree.updateRange(x, y);
        }
    }

    int modsub(int t1, int t2)
    {
        int res = t1 - t2;
        if(res < 0) res += MOD;

        return res;
    }

    bool BIT(int& mask, int& j)
    {
        return (mask & MASK(j));
    }

    int64_t Abs(int64_t t1)
    {
        if(t1 < 0) return -t1;
        return t1;
    }

    int MASK(int j)
    {
        return (1 << j);
    }
};

void __startup()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
//
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
}

int main()
{
    __startup();
    int t = 1;
//    cin >> t;

    for(int i = 1; i <= t; i++)
    {
        Solution().solve();
    }

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	9 ms	3420 KB	Output is correct
5	Correct	11 ms	4188 KB	Output is correct
6	Correct	13 ms	4060 KB	Output is correct
7	Correct	10 ms	4188 KB	Output is correct
8	Correct	83 ms	29008 KB	Output is correct
9	Correct	178 ms	52068 KB	Output is correct
10	Correct	162 ms	55388 KB	Output is correct
11	Correct	168 ms	59672 KB	Output is correct
12	Correct	183 ms	61288 KB	Output is correct
13	Correct	160 ms	72744 KB	Output is correct
14	Correct	174 ms	73288 KB	Output is correct
15	Correct	284 ms	132192 KB	Output is correct
16	Correct	265 ms	132964 KB	Output is correct
17	Correct	166 ms	75828 KB	Output is correct
18	Correct	167 ms	75772 KB	Output is correct
19	Correct	292 ms	136172 KB	Output is correct
20	Correct	266 ms	136132 KB	Output is correct