Submission #735544

#	Time	Username	Problem	Language	Result	Execution time	Memory
735544		PoPularPlusPlus	Sterilizing Spray (JOI15_sterilizing)	C++17	75 / 100	680 ms	524288 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

bool remender(ll a , ll b){return a%b;}

//freopen("problemname.in", "r", stdin);
//freopen("problemname.out", "w", stdout);

int k;

struct item {
	vector<ll> vec;
	int cnt;
};

struct Seg {
	int siz;
	vector<item> v;
	
	void init(int n){
		siz = 1;
		while(siz < n)siz *= 2;
		
		v.resize(siz * 2);
	}
	
	item single(int x){
		item res;
		res.cnt = 0;
		while(x > 0){
			//cout << x << endl;
			res.vec.pb(x);
			x /= k;
		}
		reverse(all(res.vec));
		return res;
	}
	
	item merge(item& a , item& b){
		item res;
		res.cnt = 0;
		int i = a.vec.size()-1;
		int j = b.vec.size()-1;
		while(i >= 0 || j >= 0){
			ll sum = 0;
			if(i >= 0)sum += a.vec[i];
			if(j >= 0)sum += b.vec[j];
			res.vec.pb(sum);
			i--;
			j--;
		}
		reverse(all(res.vec));
		return res;
	}
	
	void lazy(int x , int cnt){
		while(v[x].vec.size() && cnt){
			v[x].vec.pop_back();
			cnt--;
		}
	}
	
	void build(vector<int>& a , int x , int lx , int rx){
		if(rx - lx == 1){
			if(lx < a.size()){
				v[x] = single(a[lx]);
			}
			v[x].cnt = 0;
			return;
		}
		int m = (lx + rx)/2;
		build(a,2*x+1,lx,m);
		build(a,2*x+2,m,rx);
		v[x] = merge(v[2 * x + 1] , v[2 * x + 2]);
	}
	
	void build(vector<int>& a){
		build(a , 0 , 0 , siz);
	}
	
	void remove(int l , int r , int x, int lx , int rx){
		if(lx >= r || l >= rx)return;
		if(lx >= l && rx <= r){
			v[x].cnt++;
			if(v[x].vec.size()){
				v[x].vec.pop_back();
			}
			return;
		}
		v[2*x+1].cnt += v[x].cnt;
		v[2*x+2].cnt += v[x].cnt;
		lazy(2*x+1,v[x].cnt);
		lazy(2*x+2,v[x].cnt);
		v[x].cnt = 0;
		int m = (lx + rx)/2;
		remove(l,r,2*x+1,lx,m);
		remove(l,r,2*x+2,m,rx);
		v[x] = merge(v[2*x+1],v[2*x+2]);
	}
	
	void remove(int l , int r){
		remove(l , r , 0 , 0 , siz);
	}
	
	void set(int i , int val , int x , int lx , int rx){
		if(rx - lx == 1){
			v[x] = single(val);
			return;
		}
		v[2*x+1].cnt += v[x].cnt;
		v[2*x+2].cnt += v[x].cnt;
		lazy(2*x+1,v[x].cnt);
		lazy(2*x+2,v[x].cnt);
		v[x].cnt = 0;
		int m = (lx + rx)/2;
		if(i < m)set(i , val , 2 * x + 1 , lx , m);
		else set(i , val , 2 * x + 2 , m , rx);
		v[x] = merge(v[2 * x + 1] , v[2 * x + 2]);
	}
	
	void set(int i , int val){
		set(i , val , 0 , 0 , siz);
	}
	
	ll sum(int l , int r , int x , int lx , int rx){
		if(lx >= r || l >= rx)return 0;
		if(lx >= l && rx <= r){
			if(v[x].vec.size()){
				return v[x].vec.back();
			}
			return 0;
		}
		v[2*x+1].cnt += v[x].cnt;
		v[2*x+2].cnt += v[x].cnt;
		lazy(2*x+1,v[x].cnt);
		lazy(2*x+2,v[x].cnt);
		v[x].cnt = 0;
		int m = (lx + rx)/2;
		ll res = sum(l , r , 2 * x + 1 , lx , m);
		res += sum(l , r , 2 * x +2 , m , rx);
		v[x] = merge(v[2*x+1],v[2*x+2]);
		return res;
	}
	
	ll sum(int l , int r){
		return sum(l , r , 0 , 0 , siz);
	}
};

void solve(){
	int n,q;
	cin >> n >> q >> k;
	vector<int> arr(n);
	for(int i = 0; i < n; i++)cin >> arr[i];
	Seg st;
	st.init(n+1);
	//cout << "came1" << endl;
	st.build(arr);
	//cout << "came" << endl;
	while(q--){
		int a , b , c;
		cin >> a >> b >> c;
		if(a == 1){
			st.set(b - 1 , c);
		}
		else if(a == 2){
			st.remove(b - 1 , c);
		}
		else {
			cout << st.sum(b-1,c) << '\n';
		}
		//cout << st.sum(0,5) << ' ';
		//cout << "Came" << endl;
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

Compilation message (stderr)

sterilizing.cpp: In member function 'void Seg::build(std::vector<int>&, int, int, int)':
sterilizing.cpp:80:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    if(lx < a.size()){
      |       ~~~^~~~~~~~~~

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