oj.uz

Submission #318655

# Submission time Handle Problem Language Result Execution time Memory
318655 2020-11-02T19:07:52 Z CaroLinda Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 235 ms 2916 KB 
#include <bits/stdc++.h>

const int MAXN = 1e5+10 ;

using namespace std ;

int N , Q , K ;

struct SimpleSeg
{
	long long tree[MAXN*4] ;	

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

	void upd(int pos, int l, int r, int k, long long val )
	{
		if( l == r ) return (void)(tree[pos] = val) ;

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

		tree[pos] = tree[pos<<1] + tree[pos<<1|1] ;

	}

	void spray(int pos, int l, int r, int beg, int en )
	{
		if( K == 1 || tree[pos] == 0LL || l > en || r < beg ) return ;

		if( l == r ) return (void)(tree[pos] /= K  ) ;

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

		tree[pos] = tree[pos<<1] + tree[pos<<1|1] ;
	}

	long long qry(int pos, int l, int r, int beg, int en )
	{
		if( l > en || r < beg ) return 0LL ;
		if( l >= beg && r <= en ) return tree[pos] ;

		long long al = qry(pos<<1 , l , m(l,r) , beg, en ) ;
		long long ar = qry(pos<<1|1 , m(l,r)+1 , r , beg, en ) ;

		return al + ar ;

	}

} seg ;

int main()
{
	scanf("%d %d %d", &N, &Q, &K ) ;

	for(int i = 1 ; i <= N ; i++ )
	{
		long long trash ;
		scanf("%lld", &trash) ;

		seg.upd(1,1,N, i, trash ) ;

	}

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

		if( t == 1 ) seg.upd(1,1,N,l , r ) ;
		else if(t == 2 ) seg.spray(1,1,N, l, r ) ;
		else if(t == 3 ) printf("%lld\n", seg.qry(1,1,N, l, r ) ) ;

	}

}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |  scanf("%d %d %d", &N, &Q, &K ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |   scanf("%lld", &trash) ;
      |   ~~~~~^~~~~~~~~~~~~~~~
sterilizing.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |   scanf("%d %d %d", &t, &l, &r ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 1892 KB Output is correct
2 Correct 54 ms 1764 KB Output is correct
3 Correct 54 ms 2660 KB Output is correct
4 Correct 71 ms 2788 KB Output is correct
5 Correct 80 ms 2916 KB Output is correct
6 Correct 84 ms 2916 KB Output is correct
7 Correct 79 ms 2916 KB Output is correct
8 Correct 81 ms 2916 KB Output is correct
9 Correct 77 ms 2916 KB Output is correct
10 Correct 79 ms 2916 KB Output is correct
11 Correct 77 ms 2916 KB Output is correct
12 Correct 81 ms 2892 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 492 KB Output is correct
2 Correct 18 ms 1388 KB Output is correct
3 Correct 26 ms 1516 KB Output is correct
4 Correct 55 ms 876 KB Output is correct
5 Correct 82 ms 2412 KB Output is correct
6 Correct 79 ms 2412 KB Output is correct
7 Correct 75 ms 2664 KB Output is correct
8 Correct 82 ms 2604 KB Output is correct
9 Correct 76 ms 2412 KB Output is correct
10 Correct 75 ms 2540 KB Output is correct
11 Correct 76 ms 2404 KB Output is correct
12 Correct 75 ms 2432 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 1508 KB Output is correct
2 Correct 94 ms 1632 KB Output is correct
3 Correct 100 ms 1508 KB Output is correct
4 Correct 113 ms 1288 KB Output is correct
5 Correct 144 ms 2684 KB Output is correct
6 Correct 158 ms 2660 KB Output is correct
7 Correct 138 ms 2744 KB Output is correct
8 Correct 182 ms 2660 KB Output is correct
9 Correct 173 ms 2660 KB Output is correct
10 Correct 185 ms 2664 KB Output is correct
11 Correct 144 ms 2660 KB Output is correct
12 Correct 235 ms 2788 KB Output is correct