#include <bits/stdc++.h>
// author : a1abay
#define all(v) v.begin(), v.end()
#define int ll
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a*b / (__gcd(a, b)))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const int inf = 1e9 + 7;
const int inff = 1e18 + 7;
const int sz = 1e5 + 5;
using namespace std;
int n, cnt = 1;
vector<int> li(sz << 3, -1), ri(sz << 3, -1);
vector<int> sg(sz << 3, 0), lz(sz << 3, 0);
void relax(int ind, int l, int r)
{
if(!lz[ind])return;
if(li[ind] == -1)li[ind] = ++cnt;
if(ri[ind] == -1)ri[ind] = ++cnt;
//cout << "relx : " << l << " " << r << endl;
if(l == r)
{
sg[ind] = 1;
lz[ind] = 0;
return;
}
sg[ind] = r - l + 1;
lz[li[ind]] = lz[ind];
lz[ri[ind]] = lz[ind];
lz[ind] = 0;
}
int get(int ind, int l, int r, int lx, int rx)
{
if(li[ind] == -1)li[ind] = ++cnt;
if(ri[ind] == -1)ri[ind] = ++cnt;
relax(ind, l, r);
if(l > rx || r < lx)return 0;
if(lx <= l && r <= rx)return sg[ind];
int mid = (l + r) >> 1, res = 0;
if(lx <= mid)res += get(li[ind], l, mid, lx, rx);
else relax(li[ind], l, mid);
if(mid + 1 <= rx)res += get(ri[ind], mid + 1, r, lx, rx);
else if(mid < r)relax(ri[ind], mid + 1, r);
return res;
}
void upd(int ind, int l, int r, int lx, int rx)
{
if(li[ind] == -1)li[ind] = ++cnt;
if(ri[ind] == -1)ri[ind] = ++cnt;
//cout << "IN : " << l << " " << r << " " << sg[ind] << endl;
relax(ind, l, r);
if(lx <= l && r <= rx)
{
lz[ind] = 1;
relax(ind, l, r);
return;
}
int mid = (l + r) >> 1;
if(lx <= mid)upd(li[ind], l, mid, lx, rx);
else relax(li[ind], l, mid);
if(mid + 1 <= rx)upd(ri[ind], mid + 1, r, lx, rx);
else if(mid < r) relax(ri[ind], mid + 1, r);
sg[ind] = sg[li[ind]] + sg[ri[ind]];
//cout << "OUT : " << endl;;
//cout << l << " " << mid << " " << sg[li[ind]] << endl;
//cout << mid + 1 << " " << r << " " << sg[ri[ind]] << endl;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
int c = 0;
while(n--)
{
int d, x, y;
cin >> d >> x >> y;
if(d == 1)
{
int val = get(1, 1, 1e9, x + c, y + c);
c += val;
cout << val << '\n' ;
}
else
{
upd(1, 1, 1e9, x + c, y + c);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
25688 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
25436 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
