oj.uz

답안 #222853

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
222853 2020-04-14T08:38:30 Z arnold518 Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 1898 ms 524292 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<int> tree[MAXN*4+10];
int lazy[MAXN*4+10];
 
vector<int> operator + (const vector<int> &p, const vector<int> &q)
{
	int i, j;
	vector<int> 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];
		while(t) tree[node].push_back(t%K), t/=K;
		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(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<int>().swap(tree[node]);
		while(t) tree[node].push_back(t%K), t/=K;
		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<int> 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<int>();
	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<int> 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<int> operator+(const std::vector<int>&, const std::vector<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:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sterilizing.cpp: In function 'void busy(int, int, int)':
sterilizing.cpp:45:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
sterilizing.cpp: In function 'void update(int, int, int, int)':
sterilizing.cpp:58:7: warning: unused variable 'i' [-Wunused-variable]
   int i, j;
       ^
sterilizing.cpp:58:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j;
          ^
sterilizing.cpp:65:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sterilizing.cpp: In function 'std::vector<int> query(int, int, int, int, int)':
sterilizing.cpp:76: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:90:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:98:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
sterilizing.cpp:100: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:101: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:106: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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 9856 KB Output is correct
2 Runtime error 1818 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1898 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 10368 KB Output is correct
2 Correct 50 ms 12800 KB Output is correct
3 Correct 61 ms 12800 KB Output is correct
4 Correct 147 ms 12408 KB Output is correct
5 Correct 214 ms 16888 KB Output is correct
6 Correct 222 ms 17016 KB Output is correct
7 Runtime error 1154 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 238 ms 17120 KB Output is correct
2 Correct 264 ms 18808 KB Output is correct
3 Correct 258 ms 23672 KB Output is correct
4 Correct 299 ms 17400 KB Output is correct
5 Correct 391 ms 26232 KB Output is correct
6 Correct 421 ms 28024 KB Output is correct
7 Correct 384 ms 26104 KB Output is correct
8 Correct 490 ms 37112 KB Output is correct
9 Correct 392 ms 29432 KB Output is correct
10 Correct 471 ms 37216 KB Output is correct
11 Correct 358 ms 27768 KB Output is correct
12 Correct 518 ms 40568 KB Output is correct