#include<bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
//#define int long long
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rof(i,a,b) for(int i=a;i>=b;i--)
typedef pair<int,int> pii;
#define F first
#define S second
typedef vector<int> vi;
#define pb push_back
#define ft front()
#define bk back()
#define tp top()
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define ms(a,x) memset(a,x,sizeof(a))
#define lc p<<1
#define rc (p<<1)|1
const int Size=1e6;
struct Node{
int len,cnt,tg;
}seg[4*Size+20],init;
Node add(Node nd1,Node nd2){
Node nd;
nd.len=nd1.len+nd2.len;
nd.tg=nd1.tg&nd2.tg;
nd.cnt=(nd1.tg?nd1.len:nd1.cnt)+(nd2.tg?nd2.len:nd2.cnt);
return nd;
}
void setnode(int p,int val){
seg[p].tg+=val;
}
void push_up(int p){
seg[p]=add(seg[lc],seg[rc]);
}
void push_down(int p){
if(seg[p].tg){
setnode(lc,seg[p].tg);
setnode(rc,seg[p].tg);
}
}
void build(int s,int t,int p){
if(s==t){
seg[p].len=1;
return ;
}
int m=s+((t-s)>>1);
build(s,m,lc);
build(m+1,t,rc);
push_up(p);
}
void modify(int l,int r,int s,int t,int p,int val){
if(l<=s&&t<=r){
setnode(p,val);
return ;
}
push_down(p);
int m=s+((t-s)>>1);
if(l<=m) modify(l,r,s,m,lc,val);
if(m<r) modify(l,r,m+1,t,rc,val);
push_up(p);
}
Node query(int l,int r,int s,int t,int p){
if(l<=s&&t<=r) return seg[p];
int m=s+((t-s)>>1);
push_down(p);
Node res=init;
if(l<=m) res=add(res,query(l,r,s,m,lc));
if(m<r) res=add(res,query(l,r,m+1,t,rc));
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int m,c=0;
cin>>m;
build(1,Size,1);
assert(m<=10000);
while(m--){
int d,x,y;
cin>>d>>x>>y;
if(d==1){
c=query(x+c,y+c,1,Size,1).cnt;
cout<<c<<"\n";
}
else modify(x+c,y+c,1,Size,1,1);
}
return 0;
}
/*
check:
1.read problem statement correctly
2.int overflow
3.array out of bound
4.special case(0 or 1)
5.time complexity
6.try to change dimension in array!!!
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
25176 KB |
Output is correct |
| 2 |
Correct |
11 ms |
25180 KB |
Output is correct |
| 3 |
Correct |
11 ms |
25108 KB |
Output is correct |
| 4 |
Correct |
17 ms |
25180 KB |
Output is correct |
| 5 |
Correct |
19 ms |
25268 KB |
Output is correct |
| 6 |
Correct |
20 ms |
25512 KB |
Output is correct |
| 7 |
Correct |
19 ms |
25180 KB |
Output is correct |
| 8 |
Runtime error |
31 ms |
50896 KB |
Execution killed with signal 6 |
| 9 |
Halted |
0 ms |
0 KB |
- |
