Submission #919874

#	Time	Username	Problem	Language	Result	Execution time	Memory
919874		Macker	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	464 ms	139852 KiB

apple

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()

struct node{
    node* l = NULL, * r = NULL;
    int val = 0;
    int lz = 0;
};
typedef node* pnode;

void push(pnode& n){
    if(!n->l) n->l = new node();
    if(!n->r) n->r = new node();
}

void prop(pnode& n, int d){
    if(!n->lz) return;
    push(n);
    n->l->val = d / 2;
    n->r->val = d / 2;
    n->l->lz = 1;
    n->r->lz = 1;
    n->lz = 0;
}

void upd(int l, int r, pnode& n, int s = 0, int e = 2147483647){
    if(l >= e || r <= s) return;
    if(l <= s && e <= r){
        n->val = e - s;
        n->lz = 1;
        return;
    }
    push(n);
    prop(n, e - s);

    upd(l, r, n->l, s, (s + e) / 2);
    upd(l, r, n->r, (s + e) / 2, e);
    n->val = n->r->val + n->l->val;
}

int qry(int l, int r, pnode& n, int s = 0, int e = 2147483647){
    if(l >= e || r <= s) return 0;
    if(l <= s && e <= r) return n->val;
    push(n);
    prop(n, e - s);

    return qry(l, r, n->l, s, (s + e) / 2) + qry(l, r, n->r, (s + e) / 2, e);
}

int main()
{
    int m; cin >> m;
    int c = 0;
    pnode root = new node();
    for (int i = 0; i < m; i++) {
        int d, x, y; cin >> d >> x >> y;
        if(d == 1){
            int res = qry(x + c, y + c + 1, root);
            cout << res << "\n";
            c = res;
        }
        else{
            upd(x + c, y + c + 1, root);
        }
    }
    
}

• Subtask 1: 100 / 100