oj.uz

답안 #735544

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
735544 2023-05-04T10:11:55 Z PoPularPlusPlus Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 680 ms 524288 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);
	}
};

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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 372 KB Output is correct
2 Runtime error 642 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 668 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 1612 KB Output is correct
2 Correct 29 ms 6740 KB Output is correct
3 Correct 44 ms 6864 KB Output is correct
4 Correct 107 ms 4684 KB Output is correct
5 Correct 152 ms 14672 KB Output is correct
6 Correct 158 ms 14660 KB Output is correct
7 Runtime error 497 ms 524288 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 300 ms 20736 KB Output is correct
2 Correct 343 ms 20892 KB Output is correct
3 Correct 356 ms 29772 KB Output is correct
4 Correct 388 ms 13736 KB Output is correct
5 Correct 528 ms 39496 KB Output is correct
6 Correct 528 ms 39972 KB Output is correct
7 Correct 512 ms 39108 KB Output is correct
8 Correct 680 ms 64404 KB Output is correct
9 Correct 465 ms 39684 KB Output is correct
10 Correct 551 ms 64276 KB Output is correct
11 Correct 398 ms 39632 KB Output is correct
12 Correct 610 ms 64776 KB Output is correct