Submission #980885

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
980885	2024-05-12T14:51:28 Z	Hagry	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	354 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	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	14 ms	9404 KB	Output is correct
5	Correct	16 ms	11352 KB	Output is correct
6	Correct	17 ms	11100 KB	Output is correct
7	Correct	17 ms	11536 KB	Output is correct
8	Correct	144 ms	86812 KB	Output is correct
9	Correct	305 ms	150776 KB	Output is correct
10	Correct	330 ms	166700 KB	Output is correct
11	Correct	334 ms	179300 KB	Output is correct
12	Correct	348 ms	184676 KB	Output is correct
13	Correct	354 ms	215092 KB	Output is correct
14	Correct	337 ms	217428 KB	Output is correct
15	Runtime error	354 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-