# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1086279 | Flan312 | Monkey and Apple-trees (IZhO12_apple) | C++17 | 260 ms | 139628 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>
#define ll long long
#define ld long double
#define eb emplace_back
#define task ""
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int>
using namespace std;
struct node
{
int cnt;
bool lazy;
node *l, *r;
node(int cnt = 0, bool lazy = 0) : cnt(cnt), lazy(lazy)
{
l = r = nullptr;
}
};
#define check(x) if (x == nullptr) x = new node();
void assign(node *root, int l, int r, int val)
{
if (!val) return;
root -> cnt = r - l + 1;
root -> lazy = 1;
}
void down(node *root, int l, int r)
{
check(root -> l);
check(root -> r);
if (!root -> lazy) return;
int mid = l + r >> 1;
assign(root -> l, l, mid, root -> lazy);
assign(root -> r, mid + 1, r, root -> lazy);
root -> lazy = 0;
}
void update(node *root, int l, int r, int u, int v)
{
if (l > v || r < u) return;
if (l >= u && r <= v)
return assign(root, l, r, v);
down(root, l, r);
int mid = l + r >> 1;
if (u <= mid) update(root -> l, l, mid, u, v);
if (mid < v) update(root -> r, mid + 1, r, u, v);
root -> cnt = (root -> l -> cnt) + (root -> r -> cnt);
}
int query(node *root, int l, int r, int u, int v)
{
if (root == nullptr) return 0;
if (l > v || r < u) return 0;
if (l >= u && r <= v)
return root -> cnt;
down(root, l, r);
int mid = l + r >> 1;
int res = 0;
if (u <= mid) res += query(root -> l, l, mid, u, v);
if (mid < v) res += query(root -> r, mid + 1, r, u, v);
return res;
}
node *root = new node();
int t;
int main()
{
if (ifstream(task".inp")) nx
fast
cin >> t;
int c = 0;
while(t--)
{
int type, l, r;
cin >> type >> l >> r;
l += c, r += c;
if (type == 1)
{
c = query(root, 1, 1e9, l, r);
cout << c << '\n';
}
else update(root, 1, 1e9, l, r);
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |