# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1075176 | Sergio_2357 | Monkey and Apple-trees (IZhO12_apple) | C++17 | 498 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;
//#pragma GCC target("avx2")
//#pragma GCC optimization("Ofast")
//#define int long long
#define F first
#define S second
#define all(a) a.begin(), a.end()
#define vx vector
#define px pair
#define double long double
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<vii> viii;
typedef vector<viii> viiii;
template <class T>
void read(T& x)
{
cin >> x;
}
template <class T, class M>
void read(px<T, M>& p)
{
T a;
M b;
read(a);
read(b);
p = { a, b };
}
template <class T>
void read(vx<T>& v)
{
for (int i = 0; i < v.size(); i++)
read(v[i]);
}
template <class T>
void print(T x)
{
cout << x;
}
template <class T, class M>
void print(px<T, M> v)
{
print(v.F);
print(' ');
print(v.S);
print("; ");
}
template <class T>
void print(vx<T> v)
{
for (T x : v) {
print(x);
cout << ' ';
}
cout << endl;
}
struct SegTree {
struct Node {
int v = 0;
int lz = 0;
Node* L = NULL;
Node* R = NULL;
};
typedef Node* pnode;
pnode R = NULL;
int n;
void push_lz(pnode i, int l, int r) {
if (!i) return;
if (r-l <= 1) return;
if (i->L == NULL) {
i->L = new Node;
}
if (i->R == NULL) {
i->R = new Node;
}
if (i->lz != 0) {
int m = (r+l)/2;
i->L->lz = i->lz;
i->L->v = (m-l)*i->lz;
i->R->lz = i->lz;
i->R->v = (r-m)*i->lz;
i->lz = 0;
}
}
SegTree(int n) {
this -> n = n;
R = new Node;
}
void set(pnode i, int l, int r, int ql, int qr, int x) {
if (!i) return;
push_lz(i, l, r);
//cout << l << ' ' << r << endl;
if (ql <= l && r <= qr) {
i->lz = x;
i->v = (r-l)*x;
return;
}
if (r <= ql || qr <= l) {
return;
}
int m = (r+l)/2;
set(i->L, l, m, ql, qr, x);
set(i->R, m, r, ql, qr, x);
i->v = i->L->v + i->R->v;
}
void set(int l, int r, int x) {
//cout << 'a' << endl;
set(this->R, 0, n, l, r, x);
//cout << 'b' << endl;
}
int sum(pnode i, int l, int r, int ql, int qr) {
if (!i) return 0;
push_lz(i, l, r);
//cout << l << ' ' << r << endl;
if (ql <= l && r <= qr) {
return i->v;
}
if (r <= ql || qr <= l) {
return 0;
}
int m = (r+l)/2;
return sum(i->L, l, m, ql, qr) +
sum(i->R, m, r, ql, qr);
}
int sum(int l, int r) {
//cout << 'c' << endl;
return sum(this->R, 0, n, l, r);
}
};
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int M;
cin >> M;
SegTree st(1e9+100);
int C = 0;
while (M--) {
int t, l, r;
cin >> t >> l >> r;
l += C;
r += C;
if (t == 2) {
st.set(l-1, r, 1);
} else {
C = st.sum(l-1, r);
cout << C << endl;
//cout << 'd' << endl;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |