// Lazy no dynamic
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct SegTreeItem
{
int element;
};
class LazySegTree
{
public:
LazySegTree(int n)
{
this->nodes.resize(4 * n + 5, this->null);
this->pendingLazy.resize(4 * n + 5, false);
this->size = n;
}
void pointUpdate(int x, SegTreeItem val, int index, int l, int r)
{
if (pendingLazy[index])
propagateLazy(index, l, r);
if (x < l || x >= r)
return;
if (l == x && r == x + 1)
{
nodes[index] = val;
return;
}
pointUpdate(x, val, 2 * index, l, (r + l) / 2);
pointUpdate(x, val, 2 * index + 1, (r + l) / 2, r);
nodes[index] = merge(nodes[2 * index], nodes[2 * index + 1]);
}
void rangeUpdate(int x, int y, int index, int l, int r)
{
if (pendingLazy[index])
propagateLazy(index, l, r);
if (y <= l || x >= r)
return;
if (l >= x && r <= y)
{
pendingLazy[index] = true;
propagateLazy(index, l, r);
return;
}
rangeUpdate(x, y, 2 * index, l, (r + l) / 2);
rangeUpdate(x, y, 2 * index + 1, (r + l) / 2, r);
nodes[index] = merge(nodes[2 * index], nodes[2 * index + 1]);
}
SegTreeItem query(int x, int y, int index, int l, int r)
{
if (pendingLazy[index])
propagateLazy(index, l, r);
if (y <= l || x >= r)
return this->null;
if (l >= x && r <= y)
return nodes[index];
return merge(query(x, y, 2 * index, l, (r + l) / 2), query(x, y, 2 * index + 1, (r + l) / 2, r));
}
void pointUpdate(int x, SegTreeItem val)
{
pointUpdate(x, val, 1, 0, size);
}
void pointUpdate(int x, int val)
{
pointUpdate(x, {val}, 1, 0, size);
}
void rangeUpdate(int x, int y)
{
rangeUpdate(x, y, 1, 0, size);
}
SegTreeItem query(int x, int y)
{
return query(x, y, 1, 0, size);
}
private:
vector<SegTreeItem> nodes;
vector<bool> pendingLazy;
SegTreeItem null = {0};
int size;
void propagateLazy(int index, int l, int r)
{
if (l != r - 1)
{
pendingLazy[2 * index] = true;
pendingLazy[2 * index + 1] = true;
}
nodes[index].element = r - l;
pendingLazy[index] = false;
}
SegTreeItem merge(SegTreeItem a, SegTreeItem b)
{
SegTreeItem result;
result.element = a.element + b.element;
return result;
}
};
void solveCase()
{
int m = 0;
cin >> m;
LazySegTree lst(1000000);
int c = 0;
while (m--)
{
int d = 0, x = 0, y = 0;
cin >> d >> x >> y;
if (d == 1)
{
int res = lst.query(x + c, y + c + 1).element;
c += res;
cout << res << '\n';
}
else
{
lst.rangeUpdate(x + c, y + c + 1);
}
}
}
int32_t main()
{
mt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count());
if (rng() % 100000 == 0)
assert(false);
ios::sync_with_stdio(false), cin.tie(NULL);
solveCase();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
32056 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
32056 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
