Submission #980887

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
980887	2024-05-12T14:52:53 Z	Hagry	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	337 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;

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	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	13 ms	9444 KB	Output is correct
5	Correct	17 ms	11356 KB	Output is correct
6	Correct	16 ms	10964 KB	Output is correct
7	Correct	17 ms	11352 KB	Output is correct
8	Correct	168 ms	86864 KB	Output is correct
9	Correct	296 ms	150792 KB	Output is correct
10	Correct	334 ms	166640 KB	Output is correct
11	Correct	337 ms	179284 KB	Output is correct
12	Correct	328 ms	184656 KB	Output is correct
13	Correct	318 ms	215264 KB	Output is correct
14	Correct	306 ms	217416 KB	Output is correct
15	Runtime error	332 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-