#include<bits/stdc++.h>
#define ll long long
#define maxl 1e18
#define minl -(1e18)
#define f first
#define lb lower_bound
#define ub upper_bound
#define bg begin()
#define nd end()
#define rnd(x) random_shuffle((x).begin, (x).end())
#define reverse(x) reverse((x).begin(), (x).end())
#define del erase
#define ssub substr
#define tp tuple
#define pp pop_back
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define vi vector<ll>
#define vii vector<pair<ll,ll>>
#define lsb(x) (x&(-x))
#define log2(i) (__builtin_clzll(1) - __builtin_clzll(i))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) ((a*b)/gdc(a,b))
#define dbg(x) (cerr<<"["<<"R"<<":"<<__LINE__<<"]"<<#x<<" -> "<<(x)<<'\n',(x))
#define rand (rand() * (RAND_MAX + 1) + rand()) % (int)1e6
#define count(x) __builtin_popcount(x)
//nth elemtnh
const int fx[]={+1,0,-1,+0};
const int fy[]={+0,-1,0,+1};
//cout << setprecision(10) << fixed << sol << '\n'; se voglio specificare precisione
//lower_bound(arr,arr+a,valore); unique() remove dups fill(vec,number) merge() binary_search()
// per hashing polinomiale scelgo numero primo simile a tutti i caratteri che posso mettere
using namespace std;
const ll sz=123456*64;
ll cnt=2;
struct Node{
int sum;
int lzadd;
int tl;
int tr;
int l;
int r;
Node():sum(0),lzadd(0),l(-1),r(-1){ };
void merge(Node a,Node b){
sum=a.sum+b.sum;
}
};
Node seg[sz];
void propagate(ll node){
if(seg[node].lzadd){
seg[node].sum=(1+seg[node].tr-seg[node].tl)*seg[node].lzadd;
ll mid=(seg[node].tr-seg[node].tl)/2+seg[node].tl;
if(seg[node].l==-1){
seg[node].l=cnt++;
seg[seg[node].l].tl=seg[node].tl;
seg[seg[node].l].tr=mid;
}
if(seg[node].r==-1){
seg[node].r=cnt++;
seg[seg[node].r].tl=mid+1;
seg[seg[node].r].tr=seg[node].tr;
}
seg[seg[node].r].lzadd=seg[node].lzadd;
seg[seg[node].l].lzadd=seg[node].lzadd;
seg[node].lzadd=0;
}
}
void add(ll node,ll l,ll r,ll v){
propagate(node);
if(seg[node].tl>r || seg[node].tr<l)return;
if(seg[node].tl>=l && seg[node].tr<=r){
seg[node].lzadd=v;
propagate(node);
}
else{
ll mid=(seg[node].tr-seg[node].tl)/2+seg[node].tl;
if(seg[node].l==-1){
seg[node].l=cnt++;
seg[seg[node].l].tl=seg[node].tl;
seg[seg[node].l].tr=mid;
}
if(seg[node].r==-1){
seg[node].r=cnt++;
seg[seg[node].r].tl=mid+1;
seg[seg[node].r].tr=seg[node].tr;
}
if(r<=mid)add(seg[node].l,l,r,v);
else if(l>mid)add(seg[node].r,l,r,v);
else{
add(seg[node].l,l,mid,v);
add(seg[node].r,mid+1,r,v);
}
propagate(seg[node].l);
propagate(seg[node].r);
seg[node].merge(seg[seg[node].l],seg[seg[node].r]);
}
}
ll sum(ll node,ll l,ll r){
propagate(node);
if(seg[node].tl>r || seg[node].tr<l)return 0;
if(seg[node].tl>=l && seg[node].tr<=r){
return seg[node].sum;
}
else{
ll mid=(seg[node].tr-seg[node].tl)/2+seg[node].tl;
if(seg[node].l==-1){
seg[node].l=cnt++;
seg[seg[node].l].tl=seg[node].tl;
seg[seg[node].l].tr=mid;
}
if(seg[node].r==-1){
seg[node].r=cnt++;
seg[seg[node].r].tl=mid+1;
seg[seg[node].r].tr=seg[node].tr;
}
if(r<=mid) return sum(seg[node].l,l,r);
else if(l>mid)return sum(seg[node].r,l,r);
else return sum(seg[node].l,l,mid)+sum(seg[node].r,mid+1,r);
}
}
void compute(){
seg[1].sum=0;
seg[1].tl=1;
seg[1].tr=1e9+100;
ll n;
cin>>n;
ll c=0;
for(int i=0;i<n;i++){
int mode;
cin>>mode;
ll a,b;
cin>>a>>b;
// a--;b--;
if(mode==1){
c=sum(1,a+c,b+c);
cout<<c<<'\n';
}
else{
add(1,a+c,b+c,1);
}
}
/* for(int i=0;i<n;i++){
ll a;
cin>>a;
add(1,i,i,a);
}
for(int i=0;i<m;i++){
ll mode=0;
cin>>mode;
if(mode==1){
ll a,b,u;
cin>>a>>b>>u;
a--;b--;
add(1,a,b,u);
}
else{
ll k;
cin>>k;
k--;
cout<<sum(1,k,k)<<'\n';
}
}*/
}
int main(int argc, char** argv) {
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("input.txt","r",stdin);
/* freopen("snakes.out","w",stdout);*/
int t;
t=1;
// cin>>t;
for(int i=1;i<=t;i++){
// cout<<"Case #"<<i<<": "<<compute()<<'\n';
compute();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
185892 KB |
Output is correct |
| 2 |
Correct |
28 ms |
185932 KB |
Output is correct |
| 3 |
Correct |
28 ms |
185980 KB |
Output is correct |
| 4 |
Correct |
43 ms |
186136 KB |
Output is correct |
| 5 |
Correct |
42 ms |
185944 KB |
Output is correct |
| 6 |
Correct |
43 ms |
185936 KB |
Output is correct |
| 7 |
Correct |
40 ms |
186000 KB |
Output is correct |
| 8 |
Correct |
111 ms |
187216 KB |
Output is correct |
| 9 |
Correct |
217 ms |
188104 KB |
Output is correct |
| 10 |
Correct |
237 ms |
188024 KB |
Output is correct |
| 11 |
Correct |
215 ms |
188032 KB |
Output is correct |
| 12 |
Correct |
221 ms |
187988 KB |
Output is correct |
| 13 |
Correct |
221 ms |
188504 KB |
Output is correct |
| 14 |
Correct |
212 ms |
188408 KB |
Output is correct |
| 15 |
Correct |
286 ms |
188400 KB |
Output is correct |
| 16 |
Correct |
262 ms |
188616 KB |
Output is correct |
| 17 |
Correct |
187 ms |
188324 KB |
Output is correct |
| 18 |
Correct |
200 ms |
188496 KB |
Output is correct |
| 19 |
Correct |
266 ms |
188688 KB |
Output is correct |
| 20 |
Correct |
267 ms |
188500 KB |
Output is correct |
