제출 #600092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
600092		l_reho	Garage (IOI09_garage)	C++14	100 / 100	2 ms	340 KiB

garage

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second


int N, M;
vector<int> R, W;
vector<int> B;
vector<int> S;
map<int, int> mp;

void build(int p, int L, int R){
	
	if( L == R ){
		S[p] = B[L];
		return;
	}
	
	int mid = (L+R)/2;
	
	build(p*2, L, mid);
	build(p*2+1, mid+1, R);
	
	S[p] = S[p*2] + S[p*2+1];
}

void update(int p, int L, int R, int i, int v){
	if(i > R || i < L) return;
	
	if(L == R && L == i){
		B[i] = v;
		S[p] = v;
		return;
	}
	
	int mid = (L+R)/2;
	
	update(p*2, L, mid, i, v);
	update(p*2+1, mid+1, R, i, v);
	
	
	S[p] = S[p*2] + S[p*2+1];
	
}

int getSum(){
	
	int low = 0;
	int high = N-1;
	int p = 1;
	
	while(low < high){
		int mid = low + (high-low)/2;
		
		if(S[p*2] >= 1){
			high = mid;
			p = p*2;
		}else{
			low = mid+1;
			p = p*2+1;
		}
		
	}
	
		
	return low;
}

void solve(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin>>N>>M;
	
	R.assign(N, 0);
	B.assign(N, 1);
	W.assign(M, 0);
	
	S.assign(N*4+1, 0);
	
	for(int &v:R) cin>>v;
	for(int &v:W) cin>>v;
	
	queue<int> q;
	
	int ans = 0;
	
	build(1, 0, N-1);
	
	for(int i = 0; i < 2*M; i++){
		int s;
		cin>>s;
		
		
		if(s < 0){
			s = -s;
			
			int pos = mp[s-1];
			
			mp[s-1] = 0;
			
			update(1, 0, N-1, pos-1, 1);
			
			// faccio parcheggiare il primo della coda
			if(!q.empty()){
				int p = q.front();
				q.pop();
					
				int idx = getSum();
					
				update(1, 0, N-1, idx, 0);
				
				mp[p] = idx+1;
				ans += W[p] * R[idx];
				
			}
			
			continue;
		}
		
		if(q.empty()){
			int idx = getSum();
			
			if(S[1] == 0 || idx == -1)
				q.push(s-1);
			else{
				update(1, 0, N-1, idx, 0);
				mp[s-1] = idx+1;
				ans += W[s-1] * R[idx];
				
			}
			
			continue;
		}
		
		q.push(s-1);
		
		int p = q.front();
		
		int idx = getSum();
		
		if(idx != -1 && S[1] != 0){
			update(1, 0, N-1, idx, 0);
			ans += W[p] * R[idx];
			mp[p] = idx+1;
			q.pop();
		}
	}
	
	
	cout<<ans<<endl;

}

int main(){
	solve();
	return 0;
}

• Subtask 1: 100 / 100