Submission #896375

#	Time	Username	Problem	Language	Result	Execution time	Memory
896375		jhon06	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	3 ms	5212 KiB

apple

#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;
}

• Subtask 1: 0 / 100