#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=99999;
ll cnt=2;
struct Node{
ll sum;
ll lzadd;
ll tl;
ll tr;
ll l;
ll 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=sz;
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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
5212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
