Submission #169016

#	Time	Username	Problem	Language	Result	Execution time	Memory
169016		Lawliet	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	281 ms	6412 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 100010;

class SegmentTree
{
	public:

		int getLeft(int node) { return 2*node; }
		int getRight(int node) { return 2*node + 1; }

		void update(int node, int l, int r, int i, int v)
		{
			if( i < l || r < i ) return;

			if( l == r ) return void( sum[node] = v );

			int m = ( l + r )/2;

			update( getLeft(node) , l , m , i , v );
			update( getRight(node) , m + 1 , r , i , v );

			sum[ node ] = sum[ getLeft(node) ] + sum[ getRight(node) ];
		}

		void spray(int node, int l, int r, int i, int j, int K)
		{
			if( K == 1 ) return;
			if( sum[node] == 0 ) return;
			if( j < l || r < i ) return;

			if( l == r ) return void( sum[node] /= K );

			int m = ( l + r )/2;

			spray( getLeft(node) , l , m , i , j , K );
			spray( getRight(node) , m + 1 , r , i , j , K );

			sum[ node ] = sum[ getLeft(node) ] + sum[ getRight(node) ];
		}

		lli query(int node, int l, int r, int i, int j)
		{
			if( j < l || r < i ) return 0;
			if( i <= l && r <= j ) return sum[node];

			int m = ( l + r )/2;

			lli sumLeft = query( getLeft(node) , l , m , i , j );
			lli sumRight = query( getRight(node) , m + 1 , r , i , j );

			return sumLeft + sumRight;
		}

		SegmentTree() { memset( sum , 0 , sizeof(sum) ); }

	private:

		lli sum[4*MAXN];
};

int n, q, k;

SegmentTree SEG;

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

	for(int i = 1 ; i <= n ; i++)
	{
		int v;
		scanf("%d",&v);

		SEG.update( 1 , 1 , n , i , v );
	}

	for(int i = 1 ; i <= q ; i++)
	{
		int type, L, R;
		scanf("%d %d %d",&type,&L,&R);

		if( type == 1 ) SEG.update( 1 , 1 , n , L , R );
		if( type == 2 ) SEG.spray( 1 , 1 , n , L , R , k );
		if( type == 3 ) printf("%lld\n",SEG.query( 1 , 1 , n , L , R ));
	}
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&q,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&v);
   ~~~~~^~~~~~~~~
sterilizing.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&type,&L,&R);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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