Submission #807319

#	Time	Username	Problem	Language	Result	Execution time	Memory
807319		GoldLight	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1 ms	340 KiB

apple

#include <bits/stdc++.h>
using namespace std;
void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}

const int N=1e5, INF=1e9;
int cur=2, ki[4*N+1], ka[4*N+1];
bool st[4*N+1];
void upd(int ql, int qr, int l, int r, int idx){
	if(l>qr || r<ql) return;
	if(l>=ql && r<=qr){
		st[idx]=true;
		return;
	}
	int mid=(l+r)/2;
	if(ki[idx]==0) ki[idx]=cur++;
	if(ka[idx]==0) ka[idx]=cur++;
	upd(ql, qr, l, mid, ki[idx]);
	upd(ql, qr, mid+1, r, ka[idx]);
}
int query(int ql, int qr, int l, int r, int idx){
	if(l>qr || r<ql) return 0;
	if(st[idx]) return r-l+1;
	int mid=(l+r)/2, ret=0;
	if(ki[idx]!=0) ret+=query(ql, qr, l, mid, ki[idx]);
	if(ka[idx]!=0) ret+=query(ql, qr, mid+1, r, ka[idx]);
	return ret;
}
int main(){
	fast();
	int m, type, l, r, c=0; cin>>m;
	while(m--){
		cin>>type>>l>>r;
		if(type==1){
			c=query(l, r, 1, INF, 1);
			cout<<c<<'\n';
		}
		else upd(l, r, 1, INF, 1);
	}
}
/*
#define int long
const int N=1e6;
int a[N+1], st[4*N+1];
void build(int l, int r, int idx){
	if(l==r){
		st[idx]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(l, mid, 2*idx);
	build(mid+1, r, 2*idx+1);
	st[idx]=st[2*idx]+st[2*idx+1];
}
void upd(int l, int r, int idx, int k, int v){
	if(l==r){
		st[idx]+=v;
		return;
	}
	int mid=(l+r)/2;
	if(k<=mid) upd(l, mid, 2*idx, k, v);
	else upd(mid+1, r, 2*idx+1, k, v);
	st[idx]=st[2*idx]+st[2*idx+1];
}
int query(int ql, int qr, int l, int r, int idx){
	if(l>=ql && r<=qr) return st[idx];
	if(l>qr || r<ql) return 0ll;
	int mid=(l+r)/2;
	return query(ql, qr, l, mid, 2*idx)+query(ql, qr, mid+1, r, 2*idx+1);
}
signed main(){
	fast();
	int n; cin>>n;
	for(int i=1; i<=n; i++) cin>>a[i];
	build(1, n, 1);
	char type;
	int q, l, r; cin>>q;
	while(q--){
		cin>>type>>l>>r;
		if(type=='q') cout<<query(l, r, 1, n, 1)<<'\n';
		else upd(1, n, 1, l, r);
	}
}
*/
/*
const int N=5e4+5;
int a[N];
struct Node{
	int pref, suff, sum, ans;
	Node(){}
	Node(int val){
		pref=val, suff=val, sum=val, ans=val;
	}
	bool operator==(Node other) const {
		return pref==other.pref && suff==other.suff && sum==other.sum && ans==other.ans;
	}
};
Node tree[4*N];
const Node invaldi=Node(-1e9);
Node merge(Node ki, Node ka){
	if(ki==invaldi) return ka;
	if(ka==invaldi) return ki;
	Node ret=Node(0);
	ret.pref=max(ki.pref, ki.sum+ka.pref);
	ret.suff=max(ka.suff, ki.suff+ka.sum);
	ret.sum=ki.sum+ka.sum;
	ret.ans=max({ki.suff+ka.pref, ki.ans, ka.ans});
	return ret;
}
void build(int l, int r, int idx){
	if(l==r){
		tree[idx]=Node(a[l]);
		return;
	}
	int mid=(l+r)/2;
	build(l, mid, 2*idx);
	build(mid+1, r, 2*idx+1);
	tree[idx]=merge(tree[2*idx], tree[2*idx+1]);
}
void upd(int l, int r, int idx, int k, int v){
	if(l==r){
		tree[idx]=Node(v);
		return;
	}
	int mid=(l+r)/2;
	if(k<=mid) upd(l, mid, 2*idx, k, v);
	else upd(mid+1, r, 2*idx+1, k, v);
	tree[idx]=merge(tree[2*idx], tree[2*idx+1]);
}
Node query(int ql, int qr, int l, int r, int idx){
	if(l>qr || r<ql) return invaldi;
	if(l>=ql && r<=qr) return tree[idx];
	int mid=(l+r)/2;
	return merge(query(ql, qr, l, mid, 2*idx), query(ql, qr, mid+1, r, 2*idx+1));
}
int main(){
	fast();
	int n; cin>>n;
	for(int i=1; i<=n; i++) cin>>a[i];
	build(1, n, 1);
	int q, type, l, r, v; cin>>q;
	while(q--){
		cin>>l>>r;
		cout<<query(l, r, 1, n, 1).ans<<'\n';
	}
}
*/
/*
const int N=2e5, INF=2e9;
int timer=1, a[N+1], in[N+1], out[N+1], lev[N+1];
vector<vector<int>> v(N+1);
vector<pair<int,int>> val(N+1), st[4*N+1];
void dfs(int node, int p){
	in[node]=timer;
	val[timer++]={lev[node], a[node]};
	for(auto i:v[node]){
		if(i==p) continue;
		lev[i]=lev[node]+1;
		dfs(i, node);
	}
	out[node]=timer-1;
}
void build(int l, int r, int idx){
	if(l==r){
		st[idx].push_back(val[l]);
		return;
	}
	int mid=(l+r)/2;
	build(l, mid, 2*idx);
	build(mid+1, r, 2*idx+1);
	int i=0, j=0, sz1=st[2*idx].size(), sz2=st[2*idx+1].size();
	while(i<sz1 && j<sz2){
		if(st[2*idx][i]<st[2*idx+1][j]) st[idx].push_back(st[2*idx][i++]);
		else st[idx].push_back(st[2*idx+1][j++]);
	}
	while(i<sz1) st[idx].push_back(st[2*idx][i++]);
	while(j<sz2) st[idx].push_back(st[2*idx+1][j++]);
}
void build_pref(int l, int r, int idx){
	if(l==r){
		return;
	}
	int mid=(l+r)/2;
	build_pref(l, mid, 2*idx);
	build_pref(mid+1, r, 2*idx+1);
	int sz=st[idx].size();
	for(int i=1; i<sz; i++){
		st[idx][i].second=min(st[idx][i-1].second, st[idx][i].second);
	}
}
int getMin(int idx, int k){
	pair<int,int> temp={k, INF};
	int id=upper_bound(st[idx].begin(), st[idx].end(), temp)-st[idx].begin();
	id--;
	if(id==-1) return INF;
	return st[idx][id].second;
}
int query(int ql, int qr, int l, int r, int idx, int k){
	if(l>qr || r<ql) return INF;
	if(l>=ql && r<=qr){
		return getMin(idx, k);
	}
	int mid=(l+r)/2;
	return min(query(ql, qr, l, mid, 2*idx, k), query(ql, qr, mid+1, r, 2*idx+1, k));
}
int main(){
	fast();
	int n, r; cin>>n>>r;
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=1; i<n; i++){
		int x, y; cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(r, 0);
	build(1, n, 1);
	build_pref(1, n, 1);
	int ans=0, x, k, q;
	cin>>q;
	while(q--){
		cin>>x>>k;
		x=(ans+x)%n+1;
		k=(ans+k)%n;
		ans=query(in[x], out[x], 1, n, 1, lev[x]+k);
		cout<<ans<<'\n';
	}
}*/

• Subtask 1: 0 / 100