oj.uz

Submission #318653

# Submission time Handle Problem Language Result Execution time Memory
318653 2020-11-02T18:51:10 Z CaroLinda Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 1117 ms 372708 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 71 ms 100580 KB Output is correct
2 Correct 60 ms 97508 KB Output is correct
3 Correct 63 ms 97768 KB Output is correct
4 Correct 76 ms 102500 KB Output is correct
5 Correct 79 ms 103144 KB Output is correct
6 Correct 79 ms 103140 KB Output is correct
7 Correct 80 ms 103136 KB Output is correct
8 Correct 81 ms 103268 KB Output is correct
9 Correct 80 ms 103140 KB Output is correct
10 Correct 87 ms 103140 KB Output is correct
11 Correct 79 ms 103140 KB Output is correct
12 Correct 80 ms 103132 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 100580 KB Output is correct
2 Correct 103 ms 100068 KB Output is correct
3 Correct 100 ms 100580 KB Output is correct
4 Correct 108 ms 101476 KB Output is correct
5 Correct 114 ms 101860 KB Output is correct
6 Correct 120 ms 101860 KB Output is correct
7 Correct 116 ms 101988 KB Output is correct
8 Correct 117 ms 102116 KB Output is correct
9 Correct 120 ms 101880 KB Output is correct
10 Correct 117 ms 101732 KB Output is correct
11 Correct 117 ms 101864 KB Output is correct
12 Correct 116 ms 101860 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 183252 KB Output is correct
2 Correct 262 ms 136292 KB Output is correct
3 Correct 337 ms 161248 KB Output is correct
4 Correct 775 ms 329956 KB Output is correct
5 Correct 1095 ms 369892 KB Output is correct
6 Correct 1108 ms 370428 KB Output is correct
7 Correct 111 ms 100708 KB Output is correct
8 Correct 1092 ms 370404 KB Output is correct
9 Correct 871 ms 301388 KB Output is correct
10 Correct 875 ms 301156 KB Output is correct
11 Correct 881 ms 301412 KB Output is correct
12 Correct 896 ms 301740 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 277176 KB Output is correct
2 Correct 778 ms 305940 KB Output is correct
3 Correct 527 ms 221796 KB Output is correct
4 Correct 795 ms 330268 KB Output is correct
5 Correct 1107 ms 371428 KB Output is correct
6 Correct 1113 ms 371704 KB Output is correct
7 Correct 1117 ms 370500 KB Output is correct
8 Correct 1113 ms 372708 KB Output is correct
9 Correct 886 ms 303204 KB Output is correct
10 Correct 888 ms 302820 KB Output is correct
11 Correct 890 ms 303588 KB Output is correct
12 Correct 897 ms 304228 KB Output is correct