제출 #1273708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273708		nthvn	Sterilizing Spray (JOI15_sterilizing)	C++20	20 / 100	212 ms	69004 KiB

sterilizing

#include "bits/stdc++.h"
using namespace std;
#define int long long

#define fi first
#define se second
#define pii pair<int,int> 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define ll long long
const int N = 1e5+5;
const int LG = 32;
int n,q,k, a[N];

namespace sub{
	struct BIT{
		ll bit[N];
		void upd(int i, int x){
			for(;i<=n;i+=i&-i) bit[i]+=x;
		}
		ll get(int i){
			ll ans =0;
			for(;i;i-=i&-i) ans+= bit[i];
			return ans;
		}
	}bit;
	void solve(){
		for(int i=1;i<=n;i++) bit.upd(i,a[i]);
		while(q--){
			int t,u,v; cin>>t>>u>>v;
			if(t==1){
				bit.upd(u,v-bit.get(u)+bit.get(u-1));
			}
			else if(t==2){
				continue;
			}
			else cout<<bit.get(v)- bit.get(u-1)<<"\n";
		}
	}
}

struct Node{
	int dt[LG], lz;
	void combine(Node &a, Node &b){
		for(int i=0;i<LG;i++) dt[i] = a.dt[i]+ b.dt[i];
	}
	ll toNum(){
		ll ans =0;
		for(int i=LG-1;i>=0;i--){
			ans = ans*k + dt[i];
		}
		return ans;
	}
}tr[4*N];

void app_lz(Node &a, int lz){
	a.lz+= lz;
	if(lz>=LG) {
		memset(a.dt,0,sizeof(a.dt));
		return;
	}
	memmove(a.dt, a.dt+lz, (LG-lz)*sizeof(lz));
}

void down(int id){
	if(!tr[id].lz) return;
	int t= tr[id].lz;
	app_lz(tr[2*id], t);
	app_lz(tr[2*id+1],t);
	tr[id].lz =0;
}

void encode(int dt[], int x){
	memset(dt,0,sizeof(dt));
	for(int i=0;i<LG;i++){
		dt[i] = x%k;
		x/=k;
	}
}

void build(int id, int l, int r){
	if(l==r){
		encode(tr[id].dt, a[l]);
		return;
	}
	int mid=(l+r)>>1;
	build(2*id,l,mid);
	build(2*id+1,mid+1,r);
	tr[id].combine(tr[2*id], tr[2*id+1]);
}
void upd1(int id, int l, int r, int p, int v){
	if(l>p||r<p) return;
	if(l==r){
		encode(tr[id].dt, v);
		return;
	}
	int mid=(l+r)>>1;
	down(id);
	upd1(2*id,l,mid,p,v);
	upd1(2*id+1,mid+1,r,p,v);
	tr[id].combine(tr[2*id], tr[2*id+1]);
}

void upd2(int id, int l, int r, int t_l ,int t_r){
	if(l>t_r||r<t_l) return;
	if(t_l<=l&&r<=t_r){
		app_lz(tr[id], 1);
		return;
	}
	int mid=(l+r)>>1;
	down(id);
	upd2(2*id,l,mid,t_l,t_r);
	upd2(2*id+1,mid+1,r,t_l,t_r);
	tr[id].combine(tr[2*id], tr[2*id+1]);
}

ll get(int id, int l, int r, int t_l ,int t_r){
	if(l>t_r||r<t_l) return 0;
	if(t_l<=l&&r<=t_r) return tr[id].toNum();
	int mid=(l+r)>>1;
	down(id);
	return get(2*id,l,mid,t_l,t_r)+get(2*id+1,mid+1,r,t_l,t_r);
}

signed main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	if(fopen("TASK.INP", "r")){
		freopen("TASK.INP", "r", stdin);
		freopen("TASK.OUT", "w", stdout);
	}
	cin>>n>>q>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	
	if(k==1) return sub::solve(),0;
	
	
	build(1,1,n);
	while(q--){
		int t,u,v; cin>>t>>u>>v;
		if(t==1){
			upd1(1,1,n,u,v);
		}
		else if(t==2){
			upd2(1,1,n,u,v);
		}
		else cout<<get(1,1,n,u,v)<<"\n";
	}
}

컴파일 시 표준 에러 (stderr) 메시지

sterilizing.cpp: In function 'void encode(long long int*, long long int)':
sterilizing.cpp:75:28: warning: 'sizeof' on array function parameter 'dt' will return size of 'long long int*' [-Wsizeof-array-argument]
   75 |         memset(dt,0,sizeof(dt));
      |                           ~^~~
sterilizing.cpp:74:17: note: declared here
   74 | void encode(int dt[], int x){
      |                 ^
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:130:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |                 freopen("TASK.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:131:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |                 freopen("TASK.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 75