# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1209727 | abdullah_ | Monkey and Apple-trees (IZhO12_apple) | C++20 | 113 ms | 320 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pp;
#define all(a) (a).begin(), (a).end()
#define what_is(x) cerr << #x << " is " << x << '\n';
#define print(a) for (const auto &x : (a)) cout << x << ' '; cout << '\n';
const int N = 2e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e15;
struct tree {
tree *left = 0, *right = 0;
int val = 0, lazy = 0;
int low {}, high {};
tree(int l, int r) : low(l), high(r) {}
~tree() {
delete left;
delete right;
}
void apply(int newval) {
this->val = (high - low + 1);
this->lazy |= newval;
}
void push() {
if (low == high || !lazy) {
return;
}
int mid = low + (high - low) / 2;
if (!left) left = new tree(low, mid);
if (!right) right = new tree(mid + 1, high);
left->apply(lazy);
right->apply(lazy);
lazy = 0;
}
int query(int l, int r) {
if (l <= low && high <= r) return this->val;
if (l > high || low > r) return 0;
push();
int res = 0;
if (left) res += left->query(l, r);
if (right) res += right->query(l, r);
return res;
}
void update(int l, int r) {
push();
if (l > high || low > r) return;
if (l <= low && high <= r) {
apply(1);
return;
}
int mid = (low + high) / 2;
if (!left) left = new tree(low, mid);
if (!right) right = new tree(mid + 1, high);
left->update(l, r);
right->update(l, r);
int res = (left ? left->val : 0) + (right ? right->val : 0);
this->val = res;
}
};
void solve() {
int n, m;
cin >> m;
tree *root = new tree(0, 1e9 + 2);
int c= 0 ;
for (int i = 0, t, x, y; i < m; ++i) {
// char c; int x, y;
cin >> t >> x >> y;
x += c;
y += c;
if (t == 2) {
root->update(x, y);
} else {
if (x > y) swap(x, y);
int z = root->query(x, y);
cout << z << '\n';
c += z;
}
}
delete root;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("f.in", "r", stdin);
freopen("f.out", "w", stdout);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int tt = 1;
// cin >> tt;
while (tt--) {
solve();
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |