| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 871746 | andrei_c1 | Monkey and Apple-trees (IZhO12_apple) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <set>
using namespace std;
using ll = long long;
const int kInf = 1e9;
const int kMod = 1e9 + 7;
void maxSelf(int &x, int y) {
if(y > x) {
x = y;
}
}
void minSelf(int &x, int y) {
if(y < x) {
x = y;
}
}
void addSelf(int &x, int y, int mod) {
x += y;
x %= mod;
}
int add(int x, int y, int mod) {
addSelf(x, y, mod);
return x;
}
struct Chtholly {
struct Node {
int l, r;
mutable ll v;
Node() {}
Node(int l, int r = -1, ll v = 0): l(l), r(r), v(v) {}
bool operator < (const Node &oth) const {
return l < oth.l;
}
};
int n;
set<Node> tree;
Chtholly() {}
Chtholly(int n): n(n) {
tree.emplace(0, n);
}
Chtholly(int n, const vector<int> &v): n(n) {
init(v);
}
void init(const vector<int> &v) {
for(int i = 0; i < n; i++) {
tree.emplace(i, i, v[i]);
}
tree.emplace(n, n, 0);
}
set<Node>::iterator split(int x) {
auto it = tree.lower_bound(Node(x));
if(it != tree.end() && it->l == x) {
return it;
}
// assert(it != tree.begin());
it = prev(it);
if(it->r < x) {
return tree.end();
}
int l = it->l, r = it-> r;
ll v = it->v;
tree.erase(it);
tree.emplace(l, x - 1, v);
return tree.emplace(x, r, v).first;
}
void flatten(int l, int r, int v) {
auto L = split(l), R = split(r + 1);
tree.erase(L, R);
tree.emplace(l, r, v);
}
void add(int l, int r, int v) {
auto L = split(l), R = split(r + 1);
while(L != R) {
L->v += v;
L = next(L);
}
}
int query_sum(int l, int r) {
auto L = split(l), R = split(r + 1);
int res = 0;
while(L != R) {
res += L->v * (L->r - L->l + 1);
L = next(L);
}
return res;
}
int query_max(int l, int r) {
auto L = split(l), R = split(r + 1);
int res = -kInf;
while(L != R) {
maxSelf(res, L->v);
L = next(L);
}
return res;
}
int query_min(int l, int r) {
auto L = split(l), R = split(r + 1);
int res = kInf;
while(L != R) {
minSelf(res, L->v);
L = next(L);
}
return res;
}
int query_kth(int l, int r, int k) {
auto L = split(l), R = split(r + 1);
vector<pair<int, int>> v;
while(L != R) {
v.emplace_back(L->v, L->r - L->l + 1);
L = next(L);
}
sort(v.begin(), v.end());
for(const auto &it: v) {
k -= it.second;
if(k <= 0) {
return it.first;
}
}
return v.back().first;
}
};
int main() {
#ifndef EVAL
freopen("f.in", "r", stdin);
freopen("f.out", "w", stdout);
#endif
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
Chtholly ds(1e9);
int c = 0;
for(int i = 0; i < n; i++) {
int t, l, r;
cin >> t >> l >> r;
l += c;
r += c;
if(t == 2) {
ds.flatten(l, r, 1);
} else {
int res = ds.query_sum(l, r);
cout << res << '\n';
c += res;
}
}
return 0;
}