oj.uz

Submission #1042913

# Submission time Handle Problem Language Result Execution time Memory
1042913 2024-08-03T14:39:10 Z BF001 Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
 302 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long

struct node{
    int lc, rc, sum, lz;
    node(){
        lc = rc = -1;
        sum = lz = 0;
    }
};

vector<node> bit;
 
void acc(int id){
    if (bit[id].lc == -1){
        bit[id].lc = (int) bit.size();
        bit.push_back(node());
    }
    if (bit[id].rc == -1){
        bit[id].rc = (int) bit.size();
        bit.push_back(node());
    }
}

void add(int id, int l, int r, int val){
    bit[id].sum = val * (r - l + 1);
    bit[id].lz = val;
}

void down(int id, int l, int r){
    if (l == r || bit[id].lz == 0) return;
    acc(id);
    int mid = (l + r) >> 1;
    add(bit[id].lc, l, mid, bit[id].lz);
    add(bit[id].rc, mid + 1, r, bit[id].lz);
    bit[id].lz = 0;
}

void ud(int id, int l, int r, int u, int v, int val){
    if (l > v || r < u) return;
    if (l >= u && r <= v){
        add(id, l, r, val);
        return;
    }
    int mid = (l + r) >> 1;
    acc(id);
    down(id, l, r);
    ud(bit[id].lc, l, mid, u, v, val);
    ud(bit[id].rc, mid + 1, r, u, v, val);
    bit[id].sum = bit[bit[id].lc].sum + bit[bit[id].rc].sum;
}

int get(int id, int l, int r, int u, int v){
    if (l > v || r < u) return 0;
    if (l >= u && r <= v) return bit[id].sum;
    int mid = (l + r) >> 1;
    down(id, l, r);
    int t = 0, tt = 0;
    if (bit[id].lc != -1) t = get(bit[id].lc, l, mid, u, v);
    if (bit[id].rc != -1) tt = get(bit[id].rc, mid + 1, r, u, v);
    return (t + tt);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    bit.push_back(node());

    int c = 0;
    int q;
    int n = 1e9;
    cin >> q;

    while (q--){
        int typ, l, r;
        cin >> typ >>  l >> r;
        l += c; r += c;
        if (typ == 1){
            int t = get(0, 1, n, l, r);
            c = t;
            cout << t << "\n";
            continue;
        }
        ud(0, 1, n, l, r, 1);
    }    
 
    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 8 ms 4832 KB Output is correct
5 Correct 9 ms 4820 KB Output is correct
6 Correct 11 ms 4864 KB Output is correct
7 Correct 9 ms 4752 KB Output is correct
8 Correct 90 ms 34224 KB Output is correct
9 Correct 157 ms 67452 KB Output is correct
10 Correct 167 ms 67296 KB Output is correct
11 Correct 193 ms 67392 KB Output is correct
12 Correct 150 ms 67196 KB Output is correct
13 Correct 174 ms 134200 KB Output is correct
14 Correct 181 ms 134200 KB Output is correct
15 Runtime error 302 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -