# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1086380 | Sergio_2357 | Monkey and Apple-trees (IZhO12_apple) | C++17 | 681 ms | 262144 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 <bits/stdc++.h>
using namespace std;
//#define int long long
#define all(a) a.begin(), a.end()
#ifdef IS_LOCAL
#define dbg(x) {cout << #x << " = " << x << endl;}
template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
for (int i = 0; i < (int)v.size(); i++) {
os << v[i];
if (i != (int)v.size()-1)
os << ", ";
}
os << "]";
return os;
}
#else
#define dbg(x) 0
#endif
struct SegTree {
struct Node {
Node* L = NULL;
Node* R = NULL;
int v = 0;
char lz = 0;
};
typedef Node* pnode;
pnode R = NULL;
int n;
SegTree(int n_) {
n = n_;
}
void destroy(pnode& r) {
if (!r) return;
destroy(r->L);
destroy(r->R);
delete r;
}
~SegTree() {
destroy(R);
}
void push_lz(pnode& n, int l, int r) {
if (!n) {
n = new Node;
}
if (r-l <= 1) return;
if (n->lz) {
if (!n->L) {
n->L = new Node;
}
if (!n->R) {
n->R = new Node;
}
int m = (l+r)/2;
n->lz = 0;
n->L->lz = n->R->lz = 1;
n->L->v = (m-l);
n->R->v = (r-m);
}
}
void update(pnode& R, int l, int r, int ql, int qr) {
push_lz(R, l, r);
if (ql <= l && r <= qr) {
R->v = (r-l);
R->lz = 1;
return;
}
if (r <= ql || qr <= l || r == l) {
return;
}
int m = (r+l)/2;
update(R->L, l, m, ql, qr);
update(R->R, m, r, ql, qr);
R->v = R->L->v + R->R->v;
}
int query(pnode& R, int l, int r, int ql, int qr) {
push_lz(R, l, r);
if (ql <= l && r <= qr) {
return R->v;
}
if (r <= ql || qr <= l || r == l) {
return 0;
}
int m = (r+l)/2;
return query(R->L, l, m, ql, qr)+
query(R->R, m, r, ql, qr);
}
void set_1(int l, int r) {
update(R, 0, n, l, r);
}
int get_sum(int l, int r) {
return query(R, 0, n, l, r);
}
};
signed main() {
int M;
cin >> M;
int C = 0;
SegTree st(1e9+1000);
while (M--) {
int d, x, y;
cin >> d >> x >> y;
if (d == 1) {
C = st.get_sum(x+C-1, y+C);
cout << C << endl;
} else {
st.set_1(x+C-1, y+C);
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |