oj.uz

답안 #222854

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
222854 2020-04-14T08:42:42 Z arnold518 Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 719 ms 62900 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(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:59:7: warning: unused variable 'i' [-Wunused-variable]
   int i, j;
       ^
sterilizing.cpp:59:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j;
          ^
sterilizing.cpp:67: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:78: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:92:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:100:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
sterilizing.cpp:102: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:103: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:108: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 9728 KB Output is correct
2 Incorrect 13 ms 9728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 222 ms 15664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 10112 KB Output is correct
2 Correct 49 ms 12376 KB Output is correct
3 Correct 67 ms 12392 KB Output is correct
4 Correct 142 ms 11136 KB Output is correct
5 Correct 208 ms 15480 KB Output is correct
6 Correct 215 ms 15480 KB Output is correct
7 Incorrect 247 ms 18936 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 253 ms 22904 KB Output is correct
2 Correct 268 ms 21752 KB Output is correct
3 Correct 361 ms 33784 KB Output is correct
4 Correct 330 ms 19012 KB Output is correct
5 Correct 435 ms 34808 KB Output is correct
6 Correct 441 ms 36472 KB Output is correct
7 Correct 456 ms 32772 KB Output is correct
8 Correct 719 ms 53244 KB Output is correct
9 Correct 427 ms 38112 KB Output is correct
10 Correct 545 ms 53192 KB Output is correct
11 Correct 384 ms 34936 KB Output is correct
12 Correct 707 ms 62900 KB Output is correct