Submission #26411

#	Time	Username	Problem	Language	Result	Execution time	Memory
26411		zscoder	Sterilizing Spray (JOI15_sterilizing)	C++14	0 / 100	23 ms	19756 KiB

sterilizing

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

struct node
{
	ll sum;
};

node st[2000001];
int a[500001];

void combine(int id)
{
	st[id].sum=st[2*id].sum+st[2*id+1].sum;
}

void build(int id, int l, int r)
{
	if(r-l<2)
	{
		st[id].sum=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(id*2,l,mid);
	build(id*2+1,mid,r);
	combine(id);
}

void divide(int id, int l, int r, int ql, int qr, int k)
{
	if(ql>=r||l>=qr) return ;
	if(r-l<2)
	{
		st[id].sum/=k;
		return ;
	}
	if(ql<=l&&r<=qr)
	{
		if(st[id].sum==0)
		{
			return ;
		}
		int mid=(l+r)>>1;
		divide(id*2,l,mid,ql,qr,k);
		divide(id*2+1,mid,r,ql,qr,k);
		combine(id);
		return ;
	}
	int mid=(l+r)>>1;
	divide(id*2,l,mid,ql,qr,k);
	divide(id*2+1,mid,r,ql,qr,k);
	combine(id);
}

void update(int id, int l, int r, int pos, int v)
{
	if(pos>=r||pos<l) return ;
	if(r-l<2)
	{
		st[id].sum=v;
		return ;
	}
	int mid=(l+r)>>1;
	update(id*2,l,mid,pos,v);
	update(id*2+1,mid,r,pos,v);
	combine(id);
}

ll sum(int id, int l, int r, int ql, int qr)
{
	if(ql>=r||l>=qr) return 0;
	if(ql<=l&&r<=qr)
	{
		return st[id].sum;
	}
	int mid=(l+r)>>1;
	return sum(id*2,l,mid,ql,qr)+sum(id*2+1,mid,r,ql,qr);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,q;
	cin>>n>>q;
	int k; cin>>k;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	build(1,0,n);
	for(int i=0;i<q;i++)
	{
		int t; cin>>t;
		t--;
		if(t==1)
		{
			int l,r;
			cin>>l>>r;
			l--;r--;
			if(k==1) continue;
			divide(1,0,n,l,r+1,k);
		}
		else if(t==0)
		{
			int p,v;
			cin>>p>>v;
			p--;
			update(1,0,n,p,v);
		}
		else
		{
			int l,r;
			cin>>l>>r;
			l--;r--;
			cout<<sum(1,0,n,l,r+1)<<'\n';
		}
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75