#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define fi first
#define se second
int const N=1e7+3;
template <class T>
struct segmentTree
{
int arr_sz;
vector<T> seg;
vector<T> lazy;
T comb(T a,T b){return a+b;}
void pull(int x){seg[x]=comb(seg[2*x+1],seg[2*x+2]);}
void push(int x,int lx,int rx)
{
if(!lazy[x])return;
seg[x]=(rx-lx);
if(rx-lx!=1)
{
lazy[2*x+1]=1;
lazy[2*x+2]=1;
}
lazy[x]=0;
}
void init(int n,vector<T>&v)
{
int p = ceil(log2((ld)n));
arr_sz = 1<<p;
int tree_sz=arr_sz<<1;
seg.rsz(tree_sz);
lazy.rsz(tree_sz);
}
T query(int x,int lq,int rq,int lx,int rx)
{
push(x,lx,rx);
if(lq>=rx || rq<=lx)return 0;
if(lq<=lx && rq>=rx)return seg[x];
int md=(lx+rx)/2;
T lef=query(2*x+1,lq,rq,lx,md);
T rig=query(2*x+2,lq,rq,md,rx);
return comb(lef,rig);
}
T query(int lq,int rq)
{
return query(0,lq,rq,0,arr_sz);
}
void update(int x,int lq,int rq,int lx,int rx,T v)
{
push(x,lx,rx);
if(lq>=rx || rq<=lx)return;
if(lq<=lx && rq>=rx)
{
lazy[x]=v;
push(x,lx,rx);
return;
}
int md=(lx+rx)/2;
update(2*x+1,lq,rq,lx,md,v);
update(2*x+2,lq,rq,md,rx,v);
pull(x);
}
void update(int lq,int rq,T v)
{
update(0,lq,rq,0,arr_sz,v);
}
};
segmentTree<int>seg;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int m;
cin>>m;
int c=0;
vi a(N);
seg.init(N,a);
while(m--)
{
int d,x,y;
cin>>d>>x>>y;
if(d==1)
{
c=seg.query(c+x,c+y+1);
cout<<c<<'\n';
}
else
{
seg.update(c+x,c+y+1,1);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
132 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
