Submission #754969

#	Time	Username	Problem	Language	Result	Execution time	Memory
754969		ooscode	Sterilizing Spray (JOI15_sterilizing)	C++17	20 / 100	342 ms	67640 KiB

sterilizing

// IN THE NAME OF ALLAH

#include<bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
#define wall cerr << "------------------------------------" << endl
#define pb push_back
#define pob pop_back
#define F first
#define S second
#define all(x) x.begin() , x.end()
#define scan scanf
#define print printf
#define outs(x) print("%lld " , x)
#define out(x) print("%lld\n" , x)
#define in(x) scan("%lld" , &x)
#define gcd __gcd
#define endl '\n'
#define int ll

#pragma GCC optimize("Ofast")

typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll , ll> pll;
typedef pair<pii , int> piii;
typedef pair<pll , ll> plll;

const int N = 1e5+10;
const int K = 20 + 10;
const ll mod = 1e9+7;
const ll INF = 1e18+10;
const int P = 31;

int seg[4*N][K];
int la[4*N];

int n , q , k;

int a[N];

void build(int v , int tl , int tr) {
	if(tl == tr) {
		int x = a[tl];
		seg[v][0] = x;
		int o = 1;

		while(x && o < 30) {
			x /= k;
			seg[v][o++] = x;
		}
	
		return;
	}

	int tm = (tl + tr)/2;

	build(2*v , tl , tm);
	build(2*v+1 , tm+1 , tr);

	for(int i = 0 ; i < K ; i++)
		seg[v][i] = seg[2*v][i] + seg[2*v+1][i];
}

void shift(int v , int tl , int tr) {
	for(int i = 0 ; i <= K - la[v] - 1 ; i++)
		seg[v][i] = seg[v][i+la[v]];
	for(int i = K-1 ; i > K-la[v]-1 && i >= 0 ; i--)
		seg[v][i] = 0;

	if(tl != tr) {
		la[2*v] += la[v];
		la[2*v+1] += la[v];
	}

	la[v] = 0;
}

void update(int v , int tl , int tr , int pos , int x) {
	shift(v , tl , tr);

	if(tl > pos || pos > tr)
		return;

	if(tl == tr) {
		int y = x;
		seg[v][0] = y;
		int o = 1;

		while(y && o < 30) {
			y /= k;
			seg[v][o++] = y;
		}
	
		return;
	}

	int tm = (tl + tr)/2;

	update(2*v , tl , tm , pos , x);
	update(2*v+1 , tm+1 , tr , pos , x);

	for(int i = 0 ; i < K ; i++)
		seg[v][i] = seg[2*v][i] + seg[2*v+1][i];
}

void upd(int v , int tl , int tr , int l , int r) {
	shift(v , tl , tr);

	if(l > r)
		return;

	if(tl == l && tr == r) {
		la[v] = 1;
		shift(v , tl , tr);

		return;
	}

	int tm = (tl + tr)/2;

	upd(2*v , tl , tm , l , min(tm , r));
	upd(2*v+1 , tm+1 , tr , max(l , tm+1) , r);

	for(int i = 0 ; i < K ; i++)
		seg[v][i] = seg[2*v][i] + seg[2*v+1][i];
}

int ask(int v , int tl , int tr , int l , int r) {
	shift(v , tl , tr);

	if(l > r)
		return 0;

	if(tl == l && tr == r)
		return seg[v][0];

	int tm = (tl + tr)/2;

	return ask(2*v , tl , tm , l , min(tm , r)) + ask(2*v+1 , tm+1 , tr , max(l , tm+1) , r);
}

signed main()
{
	fast;

	cin >> n >> q >> k;

	for(int i = 1 ; i <= n ; i++)
		cin >> a[i];

	build(1 , 1 , n);

	if(k == 1) {
		while(q--) {
			int t , l , r;
			cin >> t >> l >> r;

			if(t == 1) 
				update(1 , 1 , n , l , r);
			else if(t == 3)
				cout << ask(1 , 1 , n , l , r) << "\n";
		}
	}
	else {
		while(q--) {
			int t , l , r;
			cin >> t >> l >> r;

			if(t == 1) 
				update(1 , 1 , n , l , r);
			else if(t == 2) 
				upd(1 , 1 , n , l , r);
			else
				cout << ask(1 , 1 , n , l , r) << "\n";
		}
	}
}

// IT'S EASY TO SEE

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