#include <iostream>
using namespace std;
const int NMAX = 1e9;
struct node
{
node *lft, *rgt;
bool lazy;
int ans;
node()
{
lft = rgt = NULL;
lazy = 0;
ans = 0;
}
};
void create(node *nod, bool ok)
{
if (ok == 0)
{
if (nod->lft == NULL)
nod->lft = new node();
}
else
{
if (nod->rgt == NULL)
nod->rgt = new node();
}
}
void propag(node *nod, int st, int dr)
{
create(nod, 0);
create(nod, 1);
if (nod->lazy == true)
{
nod->ans = dr - st + 1;
if (st != dr)
{
nod->lft->lazy = 1;
nod->rgt->lazy = 1;
}
}
nod->lazy = 0;
}
void update(node *nod, int st, int dr, int a, int b)
{
propag(nod, st, dr);
if (dr < a or st > b)
return ;
if (a <= st and dr <= b)
{
nod->lazy = 1;
propag(nod, st, dr);
return ;
}
int med = ((st + dr) >> 1);
update(nod->lft, st, med, a, b);
update(nod->rgt, med + 1, dr, a, b);
nod->ans = nod->lft->ans + nod->rgt->ans;
}
int query(node *nod, int st, int dr, int a, int b)
{
propag(nod, st, dr);
if (dr < a or st > b)
return 0;
if (a <= st and dr <= b)
{
return nod->ans;
}
int med = ((st + dr) >> 1);
int v1 = query(nod->lft, st, med, a, b);
int v2 = query(nod->rgt, med + 1, dr, a, b);
return v1 + v2;
}
int main()
{
// ifstream cin("f.in");
//ofstream cout("f.out");
int n;
cin >> n;
int ans = 0;
node *nod = new node();
while (n--)
{
int op, a, b;
cin >> op >> a >> b;
a += ans;
b += ans;
if (op == 1)
{
int val = query(nod, 1, NMAX, a, b);
cout << val << "\n";
ans += val;
}
else
update(nod, 1, NMAX, a, b);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
