oj.uz

Submission #222856

# Submission time Handle Problem Language Result Execution time Memory
222856 2020-04-14T08:43:17 Z arnold518 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 657 ms 63196 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 1e5;
 
int N, Q, K;
int C[MAXN+10];
 
vector<ll> tree[MAXN*4+10];
int lazy[MAXN*4+10];
 
vector<ll> operator + (const vector<ll> &p, const vector<ll> &q)
{
	int i, j;
	vector<ll> ret;
	ret.resize(max(p.size(), q.size()));
 
	for(i=0; i<p.size(); i++) ret[ret.size()-p.size()+i]+=p[i];
	for(i=0; i<q.size(); i++) ret[ret.size()-q.size()+i]+=q[i];
	return ret;
}
 
void init(int node, int tl, int tr)
{
	if(tl==tr)
	{
		int i, j;
		int t=C[tl];
		if(K!=1) while(t) tree[node].push_back(t%K), t/=K;
		else tree[node].push_back(t);
		reverse(tree[node].begin(), tree[node].end());
		return;
	}
	int mid=tl+tr>>1;
	init(node*2, tl, mid);
	init(node*2+1, mid+1, tr);
	tree[node]=tree[node*2]+tree[node*2+1];
}
 
void busy(int node, int tl, int tr)
{
	int i, j;
	if(K==1) return;
	if(lazy[node]==0) return;
	for(i=0; i<lazy[node] && !tree[node].empty(); i++) tree[node].pop_back();
	if(tl!=tr) lazy[node*2]+=lazy[node], lazy[node*2+1]+=lazy[node];
	lazy[node]=0;
}
 
void update(int node, int tl, int tr, int p)
{
	busy(node, tl, tr);
	if(tr<p || p<tl) return;
	if(tl==tr)
	{
		int i, j;
		int t=C[tl];
		vector<ll>().swap(tree[node]);
		if(K!=1) while(t) tree[node].push_back(t%K), t/=K;
		else tree[node].push_back(t);
		reverse(tree[node].begin(), tree[node].end());
		return;
	}
	int mid=tl+tr>>1;
	update(node*2, tl, mid, p);
	update(node*2+1, mid+1, tr, p);
	tree[node]=tree[node*2]+tree[node*2+1];
}
 
vector<ll> query(int node, int tl, int tr, int l, int r)
{
	busy(node, tl, tr);
	if(l<=tl && tr<=r) return tree[node];
	if(r<tl || tr<l) return vector<ll>();
	int mid=tl+tr>>1;
	return query(node*2, tl, mid, l, r)+query(node*2+1, mid+1, tr, l, r);
}
 
void update2(int node, int tl, int tr, int l, int r)
{
	busy(node, tl, tr);
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		lazy[node]++;
		busy(node, tl, tr);
		return;
	}
	int mid=tl+tr>>1;
	update2(node*2, tl, mid, l, r);
	update2(node*2+1, mid+1, tr, l, r);
	tree[node]=tree[node*2]+tree[node*2+1];
}
 
int main()
{
	int i, j;
 
	scanf("%d%d%d", &N, &Q, &K);
	for(i=1; i<=N; i++) scanf("%d", &C[i]);
	init(1, 1, N);
	while(Q--)
	{
		int t, l, r;
		scanf("%d%d%d", &t, &l, &r);
		if(t==1)
		{
			C[l]=r;
			update(1, 1, N, l);
		}
		else if(t==2)
		{
			update2(1, 1, N, l, r);
		}
		else
		{
			vector<ll> V=query(1, 1, N, l, r);
			ll ans=0;
			for(auto it : V) ans=ans*K+it;
			printf("%lld\n", ans);
		}
	}
}

Compilation message

sterilizing.cpp: In function 'std::vector<long long int> operator+(const std::vector<long long int>&, const std::vector<long long int>&)':
sterilizing.cpp:22:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<p.size(); i++) ret[ret.size()-p.size()+i]+=p[i];
           ~^~~~~~~~~
sterilizing.cpp:23:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<q.size(); i++) ret[ret.size()-q.size()+i]+=q[i];
           ~^~~~~~~~~
sterilizing.cpp:18:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
sterilizing.cpp: In function 'void init(int, int, int)':
sterilizing.cpp:31:7: warning: unused variable 'i' [-Wunused-variable]
   int i, j;
       ^
sterilizing.cpp:31:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j;
          ^
sterilizing.cpp:38:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sterilizing.cpp: In function 'void busy(int, int, int)':
sterilizing.cpp:46:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
sterilizing.cpp: In function 'void update(int, int, int, int)':
sterilizing.cpp:60:7: warning: unused variable 'i' [-Wunused-variable]
   int i, j;
       ^
sterilizing.cpp:60:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j;
          ^
sterilizing.cpp:68:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sterilizing.cpp: In function 'std::vector<long long int> query(int, int, int, int, int)':
sterilizing.cpp:79:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sterilizing.cpp: In function 'void update2(int, int, int, int, int)':
sterilizing.cpp:93:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:101:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
sterilizing.cpp:103: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:104:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d", &C[i]);
                      ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &t, &l, &r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9828 KB Output is correct
2 Correct 12 ms 9728 KB Output is correct
3 Correct 12 ms 10240 KB Output is correct
4 Correct 22 ms 10496 KB Output is correct
5 Correct 21 ms 10684 KB Output is correct
6 Correct 19 ms 10496 KB Output is correct
7 Correct 19 ms 10624 KB Output is correct
8 Correct 20 ms 10624 KB Output is correct
9 Correct 22 ms 11136 KB Output is correct
10 Correct 18 ms 10624 KB Output is correct
11 Correct 18 ms 10624 KB Output is correct
12 Correct 22 ms 10624 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 13944 KB Output is correct
2 Correct 253 ms 14472 KB Output is correct
3 Correct 247 ms 17816 KB Output is correct
4 Correct 315 ms 19808 KB Output is correct
5 Correct 446 ms 20420 KB Output is correct
6 Correct 397 ms 20344 KB Output is correct
7 Correct 412 ms 20364 KB Output is correct
8 Correct 399 ms 20404 KB Output is correct
9 Correct 329 ms 19340 KB Output is correct
10 Correct 354 ms 19168 KB Output is correct
11 Correct 352 ms 19320 KB Output is correct
12 Correct 349 ms 19172 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 10112 KB Output is correct
2 Correct 51 ms 12408 KB Output is correct
3 Correct 64 ms 12416 KB Output is correct
4 Correct 177 ms 11264 KB Output is correct
5 Correct 231 ms 15488 KB Output is correct
6 Correct 251 ms 15480 KB Output is correct
7 Correct 420 ms 17612 KB Output is correct
8 Correct 244 ms 16888 KB Output is correct
9 Correct 242 ms 17016 KB Output is correct
10 Correct 205 ms 16760 KB Output is correct
11 Correct 193 ms 16760 KB Output is correct
12 Correct 202 ms 16920 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 22752 KB Output is correct
2 Correct 296 ms 21924 KB Output is correct
3 Correct 376 ms 33912 KB Output is correct
4 Correct 335 ms 19184 KB Output is correct
5 Correct 455 ms 34852 KB Output is correct
6 Correct 460 ms 36600 KB Output is correct
7 Correct 437 ms 32940 KB Output is correct
8 Correct 654 ms 53472 KB Output is correct
9 Correct 443 ms 38240 KB Output is correct
10 Correct 553 ms 53564 KB Output is correct
11 Correct 400 ms 35168 KB Output is correct
12 Correct 657 ms 63196 KB Output is correct