oj.uz

Submission #754969

# Submission time Handle Problem Language Result Execution time Memory
754969 2023-06-09T07:20:12 Z ooscode Sterilizing Spray (JOI15_sterilizing) C++17
20 / 100
 342 ms 67640 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 && 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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 2 ms 1364 KB Output is correct
4 Incorrect 6 ms 1364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 34236 KB Output is correct
2 Correct 129 ms 20908 KB Output is correct
3 Correct 144 ms 66380 KB Output is correct
4 Correct 182 ms 67204 KB Output is correct
5 Correct 219 ms 67568 KB Output is correct
6 Correct 242 ms 67640 KB Output is correct
7 Correct 228 ms 67532 KB Output is correct
8 Correct 230 ms 67532 KB Output is correct
9 Correct 241 ms 67464 KB Output is correct
10 Correct 179 ms 67504 KB Output is correct
11 Correct 182 ms 67608 KB Output is correct
12 Correct 194 ms 67404 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 4368 KB Output is correct
2 Correct 73 ms 32480 KB Output is correct
3 Correct 85 ms 32388 KB Output is correct
4 Correct 216 ms 16484 KB Output is correct
5 Correct 342 ms 64716 KB Output is correct
6 Correct 330 ms 64776 KB Output is correct
7 Correct 194 ms 66008 KB Output is correct
8 Correct 340 ms 66088 KB Output is correct
9 Correct 264 ms 66000 KB Output is correct
10 Correct 248 ms 66040 KB Output is correct
11 Correct 290 ms 66044 KB Output is correct
12 Correct 251 ms 65972 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 32704 KB Output is correct
2 Correct 230 ms 32728 KB Output is correct
3 Incorrect 173 ms 32636 KB Output isn't correct
4 Halted 0 ms 0 KB -