#include <vector>
#include <iostream>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
struct node
{
int sum, lazy;
int nl, nr;
};
vector<node> aint;
const int lim = 1000000005;
void propagate(int nod, int st, int dr)
{
if(aint[nod].lazy == 0)
return;
int mij = (st + dr) / 2;
aint[aint[nod].nl].sum = (mij - st + 1);
aint[aint[nod].nr].sum = (dr - mij);
aint[aint[nod].nl].lazy = 1;
aint[aint[nod].nr].lazy = 1;
aint[nod].lazy = 0;
return;
}
void update(int nod, int st, int dr, int le, int ri)
{
if(le > ri)
return;
if(st == le && dr == ri)
{
aint[nod].sum = dr - st + 1;
aint[nod].lazy = 1;
return;
}
if(aint[nod].nl == -1)
{
aint[nod].nl = aint.size();
aint.push_back({0, 0, -1, -1});
}
if(aint[nod].nr == -1)
{
aint[nod].nr = aint.size();
aint.push_back({0, 0, -1, -1});
}
propagate(nod, st, dr);
int mij = (st + dr) / 2;
update(aint[nod].nl, st, mij, le, min(ri, mij));
update(aint[nod].nr, mij + 1, dr, max(le, mij + 1), ri);
aint[nod].sum = aint[aint[nod].nl].sum + aint[aint[nod].nr].sum;
}
int query(int nod, int st, int dr, int le, int ri)
{
if(le > ri)
return 0;
if(st == le && dr == ri)
return aint[nod].sum;
if(aint[nod].nl == -1)
{
aint[nod].nl = aint.size();
aint.push_back({0, 0, -1, -1});
}
if(aint[nod].nr == -1)
{
aint[nod].nr = aint.size();
aint.push_back({0, 0, -1, -1});
}
propagate(nod, st, dr);
int mij = (st + dr) / 2;
return query(aint[nod].nl, st, mij, le, min(ri, mij)) +
query(aint[nod].nr, mij + 1, dr, max(le, mij + 1), ri);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
aint.push_back({0, 0, -1, -1});
int m, c = 0;
cin>>m;
for(int i = 1; i <= m; i++)
{
int t, x, y;
cin>>t>>x>>y;
x += c;
y += c;
if(t == 1)
{
c = query(0, 1, lim, x, y);
cout<<c<<'\n';
}
else
{
update(0, 1, lim, x, y);
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
7 ms |
2520 KB |
Output is correct |
5 |
Correct |
9 ms |
2520 KB |
Output is correct |
6 |
Correct |
9 ms |
2520 KB |
Output is correct |
7 |
Correct |
9 ms |
2520 KB |
Output is correct |
8 |
Correct |
49 ms |
17848 KB |
Output is correct |
9 |
Correct |
118 ms |
34736 KB |
Output is correct |
10 |
Correct |
110 ms |
35260 KB |
Output is correct |
11 |
Correct |
112 ms |
34480 KB |
Output is correct |
12 |
Correct |
114 ms |
33972 KB |
Output is correct |
13 |
Correct |
112 ms |
67824 KB |
Output is correct |
14 |
Correct |
109 ms |
66480 KB |
Output is correct |
15 |
Correct |
166 ms |
132372 KB |
Output is correct |
16 |
Correct |
162 ms |
134308 KB |
Output is correct |
17 |
Correct |
124 ms |
68576 KB |
Output is correct |
18 |
Correct |
119 ms |
67528 KB |
Output is correct |
19 |
Correct |
160 ms |
133964 KB |
Output is correct |
20 |
Correct |
160 ms |
133532 KB |
Output is correct |