oj.uz

Submission #169016

# Submission time Handle Problem Language Result Execution time Memory
169016 2019-12-17T15:04:44 Z Lawliet Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 281 ms 6412 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3448 KB Output is correct
2 Correct 5 ms 3576 KB Output is correct
3 Correct 6 ms 3448 KB Output is correct
4 Correct 9 ms 3576 KB Output is correct
5 Correct 9 ms 3576 KB Output is correct
6 Correct 9 ms 3576 KB Output is correct
7 Correct 9 ms 3576 KB Output is correct
8 Correct 9 ms 3576 KB Output is correct
9 Correct 10 ms 3576 KB Output is correct
10 Correct 9 ms 3576 KB Output is correct
11 Correct 9 ms 3576 KB Output is correct
12 Correct 9 ms 3576 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 5868 KB Output is correct
2 Correct 70 ms 5592 KB Output is correct
3 Correct 72 ms 5456 KB Output is correct
4 Correct 92 ms 6100 KB Output is correct
5 Correct 105 ms 6392 KB Output is correct
6 Correct 105 ms 6412 KB Output is correct
7 Correct 105 ms 6392 KB Output is correct
8 Correct 108 ms 6392 KB Output is correct
9 Correct 95 ms 6264 KB Output is correct
10 Correct 94 ms 6264 KB Output is correct
11 Correct 95 ms 6268 KB Output is correct
12 Correct 94 ms 6264 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4088 KB Output is correct
2 Correct 25 ms 3704 KB Output is correct
3 Correct 32 ms 3804 KB Output is correct
4 Correct 70 ms 4668 KB Output is correct
5 Correct 98 ms 5112 KB Output is correct
6 Correct 97 ms 4984 KB Output is correct
7 Correct 91 ms 5112 KB Output is correct
8 Correct 102 ms 4956 KB Output is correct
9 Correct 87 ms 4856 KB Output is correct
10 Correct 87 ms 4728 KB Output is correct
11 Correct 93 ms 4728 KB Output is correct
12 Correct 87 ms 4828 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 5240 KB Output is correct
2 Correct 119 ms 5368 KB Output is correct
3 Correct 131 ms 4728 KB Output is correct
4 Correct 143 ms 5444 KB Output is correct
5 Correct 181 ms 6308 KB Output is correct
6 Correct 199 ms 6216 KB Output is correct
7 Correct 176 ms 6256 KB Output is correct
8 Correct 234 ms 6236 KB Output is correct
9 Correct 196 ms 6136 KB Output is correct
10 Correct 219 ms 6184 KB Output is correct
11 Correct 172 ms 6120 KB Output is correct
12 Correct 281 ms 6236 KB Output is correct