oj.uz

Submission #735548

# Submission time Handle Problem Language Result Execution time Memory
735548 2023-05-04T10:18:39 Z PoPularPlusPlus Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 842 ms 62488 KB 
#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);
	}
};

struct Fen {
	
	vector<ll> tree;
	
	void init(int n){
		tree.assign(n + 1 , 0LL);
	}
	
	void set(int i , ll val , int n){
		i++;
		while(i <= n){
			tree[i] += val;
			i += (i & (-i));
		}
	}
	
	ll sum(int i){
		i++;
		ll ans = 0;
		while(i > 0){
			ans += tree[i];
			i -= (i & (-i));
		}
		return ans;
	}
	
	void build(vector<int>& a){
		int n = a.size();
		for(int i = 0; i < n; i++){
			set(i , a[i] , n);
		}
	}
	
};

void solve(){
	int n,q;
	cin >> n >> q >> k;
	vector<int> arr(n);
	for(int i = 0; i < n; i++)cin >> arr[i];
	if(k == 1){
		Fen ft;
		ft.init(n+1);
		for(int i = 0; i < n; i++)ft.set(i , arr[i] , n + 1);
		while(q--){
			int a , b , c;
			cin >> a >> b >> c;
			b--;
			if(a == 1){
				ft.set(b , c - arr[b] , n + 1);
				arr[b] = c;
			}
			else if(a == 3)cout << ft.sum(c-1) - ft.sum(b-1) << '\n';
		}
		return;
	}
	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

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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 16 ms 1248 KB Output is correct
5 Correct 15 ms 1528 KB Output is correct
6 Correct 15 ms 1508 KB Output is correct
7 Correct 12 ms 1492 KB Output is correct
8 Correct 14 ms 1440 KB Output is correct
9 Correct 17 ms 2256 KB Output is correct
10 Correct 13 ms 1524 KB Output is correct
11 Correct 12 ms 1492 KB Output is correct
12 Correct 12 ms 1492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1236 KB Output is correct
2 Correct 30 ms 2640 KB Output is correct
3 Correct 33 ms 3176 KB Output is correct
4 Correct 31 ms 3904 KB Output is correct
5 Correct 39 ms 4380 KB Output is correct
6 Correct 40 ms 4428 KB Output is correct
7 Correct 59 ms 4420 KB Output is correct
8 Correct 41 ms 4428 KB Output is correct
9 Correct 38 ms 4232 KB Output is correct
10 Correct 37 ms 4280 KB Output is correct
11 Correct 41 ms 4300 KB Output is correct
12 Correct 39 ms 4300 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1108 KB Output is correct
2 Correct 26 ms 6524 KB Output is correct
3 Correct 38 ms 6528 KB Output is correct
4 Correct 96 ms 3544 KB Output is correct
5 Correct 152 ms 13348 KB Output is correct
6 Correct 153 ms 13176 KB Output is correct
7 Correct 34 ms 1612 KB Output is correct
8 Correct 165 ms 14664 KB Output is correct
9 Correct 124 ms 14468 KB Output is correct
10 Correct 115 ms 14444 KB Output is correct
11 Correct 123 ms 14452 KB Output is correct
12 Correct 158 ms 14476 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 19184 KB Output is correct
2 Correct 330 ms 19192 KB Output is correct
3 Correct 368 ms 28704 KB Output is correct
4 Correct 390 ms 11816 KB Output is correct
5 Correct 505 ms 37080 KB Output is correct
6 Correct 630 ms 37440 KB Output is correct
7 Correct 576 ms 36660 KB Output is correct
8 Correct 842 ms 61908 KB Output is correct
9 Correct 460 ms 37348 KB Output is correct
10 Correct 566 ms 61888 KB Output is correct
11 Correct 397 ms 37340 KB Output is correct
12 Correct 700 ms 62488 KB Output is correct