Submission #980881

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
980881	2024-05-12T14:35:56 Z	Hagry	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	379 ms	262144 KB

apple

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define MP make_pair
#define all(x) x.begin(),x.end()
#define Hagry ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vector<int>>;

const int OO = 1e9 + 5;
const int N = 2e5 + 5;
const int IDN = 0;
const int LAZY_IDN = 0;
#define int ll
struct Node {
    ll val, lazy;

    Node *lt, *rt;

    Node() {
        lt = rt = nullptr;
        val = IDN;
        lazy = LAZY_IDN;
    }

    void operator=(Node other) {
        val = other.val;
        lazy = other.lazy;
    }

    Node(ll val, Node *lt = nullptr, Node *rt = nullptr) {
        this->val = val;
        this->lazy = LAZY_IDN;
        this->lt = lt;
        this->rt = rt;
    }

    void addChild() {
        if (!lt) {
            lt = new Node, rt = new Node;
        }
    }
};

Node *EMPTY = new Node;

struct Seg {
    int n;
    Node *root;

    Seg(int n) {
        this->n = n;
        root = new Node();
    }

    Node merge(Node &x, Node &y) {
        return Node(x.val + y.val);
    }


    void propagate(Node *cur, int sl, int sr) {

        if (cur->lazy != LAZY_IDN) {
            cur->val = cur->lazy * (sr - sl + 1);
            cur->lt->lazy = cur->lazy;
            cur->rt->lazy = cur->lazy;
        }
        cur->lazy = LAZY_IDN;
    }

    void update(Node *cur, int ql, int qr, int sl, int sr, ll v) {
        cur->addChild();
        propagate(cur, sl, sr);
        if (ql > qr || ql > sr || sl > qr)
            return;
        if (ql <= sl && sr <= qr) {
            cur->lazy = v;
            propagate(cur, sl, sr);
            return;
        }

        int mid = (sl + sr) / 2;
        update(cur->lt, ql, qr, sl, mid, v);
        update(cur->rt, ql, qr, mid + 1, sr, v);
        *cur = merge(*(cur->lt), *(cur->rt));
    }

    void update(int ql, int qr, ll v){
        update(root, ql, qr, 0, n-1, v);
    }

    Node query(Node *cur, int ql, int qr, int sl, int sr) {
        cur->addChild();
        propagate(cur, sl, sr);
        if (ql > qr || ql > sr || sl > qr)
            return Node();
        if (ql <= sl && sr <= qr) {
            return *cur;
        }

        int mid = (sl + sr) / 2;
        Node leftRes = query(cur->lt, ql, qr, sl, mid);
        Node rightRes = query(cur->rt, ql, qr, mid + 1, sr);
        return merge(leftRes, rightRes);
    }

    Node query(int ql, int qr){
        return query(root, ql, qr, 0, n-1);
    }
};

void TC() {
    Seg tree(1e9 + 5);
    int m;
    cin >> m;


    int d, x, y, c = 0;
    for(int q=0; q<m; ++q){
        cin >> d >> x >> y;
        if(d == 1){
            int ans = tree.query(x+c, y+c).val;
            cout << ans << "\n";
            c = ans;
        }
        else
            tree.update(x+c, y+c, 1);
    }

}

int32_t main() {

    Hagry
    int t = 1;
//    cin >> t;
    while (t--) {
        TC();
        cout << '\n';
    }
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	15 ms	9564 KB	Output is correct
5	Correct	18 ms	11612 KB	Output is correct
6	Correct	17 ms	11096 KB	Output is correct
7	Correct	18 ms	11608 KB	Output is correct
8	Correct	149 ms	87744 KB	Output is correct
9	Correct	338 ms	152508 KB	Output is correct
10	Correct	358 ms	168692 KB	Output is correct
11	Correct	341 ms	180936 KB	Output is correct
12	Correct	379 ms	186584 KB	Output is correct
13	Correct	317 ms	217232 KB	Output is correct
14	Correct	323 ms	219360 KB	Output is correct
15	Runtime error	355 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-