Submission #774434

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
774434	2023-07-05T17:55:11 Z	VMaksimoski008	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	370 ms	262144 KB

apple

#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define pii pair<int, int>
#define pll pair<long long, long long>
#define debug(x) cout << #x << " = " << x << endl
#define pb push_back
#define eb emplace_back
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int mod = 1e9 + 7;
using namespace std;
 
void setIO() {
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
}
 
struct Node {
    ll sum, lazy;
    Node *l, *r;
 
    Node() {
        sum = 0, lazy = 0;
        l = nullptr, r = nullptr;
    }
 
    ~Node() {
        delete l;
        delete r;
    }
 
    void extend(ll tl, ll tr) {
        if(tl == tr) return ;
        if(this->l == nullptr) this->l = new Node();
        if(this->r == nullptr) this->r = new Node();
    }
 
    void push(ll tl, ll tr) {
        if(this->lazy == 0) return ;
        this->sum = (tr - tl + 1) * this->lazy;
 
        if(tl != tr) {
            extend(tl, tr);
            this->l->lazy = this->lazy;
            this->r->lazy = this->lazy;
        }
 
        this->lazy = 0;
    }
};
 
Node *root = new Node();
 
void update(Node *root, ll tl, ll tr, ll l, ll r, ll val) {
    root->push(tl, tr);
    if(tl > r || l > tr || tl > tr) return ;
 
    if(l <= tl && tr <= r) {
        root->lazy = val;
        root->push(tl, tr);
        return ;
    }
 
    root->extend(tl, tr);
    int tm = (tl + tr) / 2;
    update(root->l, tl, tm, l, r, val);
    update(root->r, tm+1, tr, l, r, val);
    root->sum = root->l->sum + root->r->sum;
}
 
ll query(Node *root, ll tl, ll tr, ll l, ll r) {
    if(r < tl || tr < l)
        return 0;
 
    root->push(tl, tr);
 
    if(l <= tl && tr <= r) return root->sum;
 
    root->extend(tl, tr);
    auto tm = (tl + tr) / 2;
    return query(root->l, tl, tm, l, r) +
    query(root->r, tm+1, tr, l, r);
}
 
int main() {
    setIO();
 
    int q;
    cin >> q;
 
    ll c = 0;
    while(q--) {
        int t, a, b;
        cin >> t >> a >> b;
 
        if(t == 1) {
            ll res = query(root, 1, 1e9, a+c, b+c);
            cout << res << '\n';
            c = res;
        } else {
            update(root, 1, 1e9, a+c, b+c, 1);
        }
    }
 
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	13 ms	7816 KB	Output is correct
5	Correct	15 ms	9428 KB	Output is correct
6	Correct	15 ms	9172 KB	Output is correct
7	Correct	15 ms	9424 KB	Output is correct
8	Correct	126 ms	70124 KB	Output is correct
9	Correct	256 ms	120196 KB	Output is correct
10	Correct	321 ms	134404 KB	Output is correct
11	Correct	283 ms	145260 KB	Output is correct
12	Correct	306 ms	150128 KB	Output is correct
13	Correct	261 ms	183236 KB	Output is correct
14	Correct	266 ms	185476 KB	Output is correct
15	Runtime error	370 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-