Submission #980887

#	Time	Username	Problem	Language	Result	Execution time	Memory
980887		Hagry	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	337 ms	262144 KiB

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