답안 #774437

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
774437	2023-07-05T17:57:55 Z	VMaksimoski008	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	426 ms	232656 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 {
    int sum, lazy;
    Node *l, *r;
 
    Node() {
        sum = 0, lazy = 0;
        l = nullptr, r = nullptr;
    }
 
    ~Node() {
        delete l;
        delete r;
    }
 
    void extend(int tl, int tr) {
        if(tl == tr) return ;
        if(this->l == nullptr) this->l = new Node();
        if(this->r == nullptr) this->r = new Node();
    }
 
    void push(int tl, int 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, int tl, int tr, int l, int r, short 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, int tl, int tr, int l, int 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

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	16 ms	5168 KB	Output is correct
5	Correct	14 ms	6228 KB	Output is correct
6	Correct	16 ms	6064 KB	Output is correct
7	Correct	13 ms	6212 KB	Output is correct
8	Correct	133 ms	46388 KB	Output is correct
9	Correct	263 ms	79156 KB	Output is correct
10	Correct	276 ms	88552 KB	Output is correct
11	Correct	255 ms	95844 KB	Output is correct
12	Correct	296 ms	99040 KB	Output is correct
13	Correct	254 ms	121036 KB	Output is correct
14	Correct	258 ms	122444 KB	Output is correct
15	Correct	410 ms	225844 KB	Output is correct
16	Correct	426 ms	227420 KB	Output is correct
17	Correct	281 ms	129144 KB	Output is correct
18	Correct	248 ms	128952 KB	Output is correct
19	Correct	422 ms	232652 KB	Output is correct
20	Correct	416 ms	232656 KB	Output is correct