# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1200145 | henrlly | Monkey and Apple-trees (IZhO12_apple) | C++20 | 285 ms | 305872 KiB |
// time-limit: 3000
#include <bits/stdc++.h>
using namespace std;
#define ll long long
using vll = vector<ll>;
using vvll = vector<vector<ll> >;
using mpll = map<pair<ll, ll>, ll>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int> >;
using pi = pair<int, int>;
void setIO(string name = "") {
if (name.size()) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
void solve() {
return;
}
struct Node {
Node *left = nullptr;
Node *right = nullptr;
ll cur = 0;
ll lazy = 0;
};
const ll MAXN = 1000000000;
void apply(Node *n, int len, int val) {
n->cur += val * len;
n->lazy += val;
}
void push_down(Node *n, int l, int r) {
if (n == nullptr) return;
if (n->left == nullptr) n->left = new Node;
if (n->right == nullptr) n->right = new Node;
int mid = (l+r)/2;
apply(n->left, mid-l+1, n->lazy);
apply(n->right, r-mid, n->lazy);
n->lazy = 0;
}
ll range(Node *n, int li, int ri, int l=0, int r=MAXN-1) {
if (n == nullptr) return 0ll;
push_down(n, l, r);
if (li <= l && ri >= r) return n->cur;
if (li > r || ri < l) return 0ll;
int mid = (l+r)/2;
ll res = range(n->left, li, ri, l, mid) + range(n->right, li, ri, mid+1, r);
n->cur = (n->left == nullptr ? 0 : n->left->cur) + (n->right == nullptr ? 0 : n->right->cur);
return res;
}
void ripe(Node *n, int li, int ri, int l=0, int r=MAXN-1) {
if (n == nullptr) return;
push_down(n, l, r);
if (li <= l && ri >= r) {
n->cur = r-l+1;
n->lazy = 1;
n->left = nullptr;
n->right = nullptr;
return;
}
if (li > r || ri < l) return;
if (n->left == nullptr) n->left = new Node;
if (n->right == nullptr) n->right = new Node;
int mid = (l+r)/2;
ripe(n->left, li, ri, l, mid);
ripe(n->right, li, ri, mid+1, r);
n->cur = n->left->cur + n->right->cur;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// setIO("test");
int m; cin >> m;
ll c = 0;
Node root;
while (m--) {
int t, a, b; cin >> t >> a >> b;
a--;b--;
if (t == 1) {
c = range(&root, a+c, b+c);
cout << c << endl;
} else {
ripe(&root, a+c, b+c);
}
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |