oj.uz

Submission #754967

# Submission time Handle Problem Language Result Execution time Memory
754967 2023-06-09T07:10:57 Z ooscode Sterilizing Spray (JOI15_sterilizing) C++17
0 / 100
 367 ms 190428 KB 
// 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) {
			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) {
			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);

	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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Runtime error 222 ms 190428 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 213 ms 161200 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 4732 KB Output is correct
2 Correct 58 ms 32784 KB Output is correct
3 Correct 80 ms 32880 KB Output is correct
4 Correct 228 ms 17564 KB Output is correct
5 Correct 328 ms 66204 KB Output is correct
6 Correct 367 ms 66272 KB Output is correct
7 Runtime error 123 ms 130476 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 34152 KB Output is correct
2 Correct 248 ms 34564 KB Output is correct
3 Incorrect 168 ms 33760 KB Output isn't correct
4 Halted 0 ms 0 KB -