Submission #1188630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188630		sonya	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	0 ms	320 KiB

apple

#include <iostream>
#include <vector>
using namespace std;

struct node {
    int cl = 0, cr = 0;
    int st = 0;
};

int br = 2;
const int MAX = 1e9;
vector<node> p(4);

void create(int h){
    if (p[h].cl == 0) {
        p[h].cl = br++;
        p[h].cr = br++;
        if ((int)p.size() <= br) p.resize(br + 2);
    }
}

void update(int node, int l, int r, int pos, int val){
    if (l == r) {
        p[node].st = val;
        return;
    }

    create(node);
    int mid = (l + r) / 2;
    if (pos <= mid) update(p[node].cl, l, mid, pos, val);
    else update(p[node].cr, mid + 1, r, pos, val);

    p[node].st = p[p[node].cl].st + p[p[node].cr].st;
}

int query(int node, int l, int r, int ql, int qr){
    if (l > qr || r < ql || node == 0) return 0;
    if (l >= ql && r <= qr) return p[node].st;

    create(node);
    int mid = (l + r) / 2;
    return query(p[node].cl, l, mid, ql, qr) + query(p[node].cr, mid + 1, r, ql, qr);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int m;
    cin >> m;

    while(m--){
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 1) {
            cout << query(1, 1, MAX, x, y) << '\n';
        } else {
            for(int i = x; i <= y; i++){
                update(1, 1, MAX, i, 1);
            }
        }
    }
    return 0;
}

• Subtask 1: 0 / 100