답안 #896379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
896379	2024-01-01T10:48:57 Z	jhon06	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	286 ms	188688 KB

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

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	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