Submission #318653

#	Time	Username	Problem	Language	Result	Execution time	Memory
318653		CaroLinda	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	1117 ms	372708 KiB

sterilizing

#include <bits/stdc++.h>

#define sz(x) (int)(x.size() )
#define ll long long
#define all(x) x.begin(),x.end()
#define CTE 30

const int MAXN = 1e5+10 ;

using namespace std ;

struct Node
{
	int qtdLazy ;
	long long sums[CTE] ;

	Node() 
	{
		qtdLazy = 0 ;
		for(int i = 0 ; i < CTE ; i++ ) sums[i] = 0LL ;
	}
} ;


struct Seg
{
	Node tree[MAXN*4] ;

	int m(int l, int r ) { return (l+r)>>1 ; }

	void refresh(int pos, int l, int r )		
	{
		if(tree[pos].qtdLazy == 0 ) return ;

		Node &ptr = tree[pos] ;

		for(int i = 0 ; i < CTE ; i++ )
		{	
			if( i + ptr.qtdLazy < CTE )
				ptr.sums[i] = ptr.sums[ i+ptr.qtdLazy ] ;
			else ptr.sums[i] = 0 ;
		}

		if( l == r ) return (void)(ptr.qtdLazy = 0) ;

		tree[pos<<1].qtdLazy += ptr.qtdLazy ;
		tree[pos<<1|1].qtdLazy += ptr.qtdLazy ;

		ptr.qtdLazy = 0 ;

	}

	void merge(Node &v, Node &l, Node &r )
	{
		for(int i = 0 ;i < CTE ; i++ )
			v.sums[i] = l.sums[i] + r.sums[i] ;
	}

	//Don't forget to erase the value that was there before updating

	void upd(int pos, int l, int r, int k, vector<long long> toSum )
	{
		refresh(pos,l,r) ;
		
		for(int i = 0 ; i < CTE  ; i++ )
			tree[pos].sums[i] += toSum[i] ;

		if( l == r ) return ;
			
		if( k <= m(l,r) ) upd(pos<<1 , l, m(l,r) , k , toSum ) ;
		else upd(pos<<1|1 , m(l,r)+1, r, k , toSum ) ;

	}

	void spray(int pos, int l, int r, int beg, int en )
	{
		refresh(pos,l,r) ;
		
		if( l > en || r < beg ) return ;
		if( l >= beg && r <= en ) 
		{	
			tree[pos].qtdLazy++ ;
			refresh(pos,l,r) ;
			return ;
		}

		spray(pos<<1 , l ,m(l,r) , beg, en ) ;
		spray(pos<<1|1 , m(l,r)+1, r, beg, en ) ;

		merge( tree[pos], tree[pos<<1] , tree[pos<<1|1] ) ;

	}

	Node qry(int pos, int l, int r, int beg, int en )
	{
		if( l > en || r <beg ) return *(new Node() ) ;

		refresh(pos,l,r ) ;

		if( l >= beg && r <= en ) return tree[pos] ;

		Node a = qry(pos<<1 ,l , m(l,r) , beg, en ) ;
		Node b = qry(pos<<1|1 , m(l,r)+1, r, beg, en ) ;
		Node v ;

		merge(v,a,b) ;

		return v ;

	}

} seg ;

int n , k , q ;

long long miniBit[MAXN] ;
void upd(int i, long long val ) { for(; i < MAXN ; i += i & -i ) miniBit[i] += val ; }
long long qry(int i )
{
	long long tot = 0 ;
	for(; i > 0 ; i -= i &-i ) tot += miniBit[i] ;
	return tot ;
}
void solve1()
{
	vector<long long> plate(n+1) ;

	for(int i = 1 ; i <= n ; i++ )
	{
		scanf("%lld", &plate[i] ) ;
		upd(i, plate[i]) ;
	}		

	for(int i = 1 , t ,l ,r ; i <= q ; i++ )
	{
		scanf("%d%d%d", &t, &l, &r ) ;

		if(t == 1 )
		{
			upd( l , -plate[l] + r ) ;
			plate[l] = r ;
		}
		else if( t == 3 ) printf("%lld\n", qry(r) - qry(l-1) ) ;
	}

	exit(0) ;

}

int main()
{
	scanf("%d %d %d", &n, &q, &k ) ;

	if(k == 1 ) solve1() ;

	for(int i = 1 , c ; i <= n ; i++ )
	{
		vector<long long> toSum(CTE);
		scanf("%lld", &toSum[0] ) ;

		for(int j = 1 ; j < CTE ; j++ )
			toSum[j] = toSum[j-1]/k ;	

		seg.upd(1,1,n, i, toSum ) ;
	}

	for(int i = 1 , t , l, r ; i <= q ; i++ )
	{
		scanf("%d %d %d", &t, &l, &r ) ;

		Node ans ;

		if(t == 1 )
		{
			ans = seg.qry(1,1,n, l , l ) ;

			vector<long long> toSum(CTE) ;

			toSum[0] = r ;

			for(int j = 1 ; j < CTE ; j++ ) toSum[j] = toSum[j-1]/k ;
			for(int j = 0 ; j < CTE ; j++ ) toSum[j] -= ans.sums[j] ;


			seg.upd(1,1,n, l , toSum ) ;

		}
		else if( t == 2 ) seg.spray(1,1,n, l, r ) ;
		else
		{
			ans = seg.qry(1,1,n, l, r ) ;
			printf("%lld\n", ans.sums[0] ) ;
		}
	}

}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:156:18: warning: unused variable 'c' [-Wunused-variable]
  156 |  for(int i = 1 , c ; i <= n ; i++ )
      |                  ^
sterilizing.cpp: In function 'void solve1()':
sterilizing.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |   scanf("%lld", &plate[i] ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:136:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  136 |   scanf("%d%d%d", &t, &l, &r ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:152:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  152 |  scanf("%d %d %d", &n, &q, &k ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:159:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  159 |   scanf("%lld", &toSum[0] ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:169:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  169 |   scanf("%d %d %d", &t, &l, &r ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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