제출 #941229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
941229		NotLinux	Election (BOI18_election)	C++17	0 / 100	8 ms	608 KiB

election

//author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
const int inf = 1e9 + 7;
struct SEGT{
	vector < pair < int , int > > tree;
	vector < int > lzt;
	int tree_size;
	bool is_inverse = 0;
	SEGT(int x , bool bl){
		tree_size = x + 3;
		tree.assign(4 * tree_size , {0,inf});
		lzt.assign(4 * tree_size , 0);
		is_inverse = bl;
		build(1,0,tree_size);
	}
	void build(int ind , int l , int r){
		if(l == r){
			tree[ind].second = l * (is_inverse ? -1 : 1);
			return;
		}
		int mid = (l + r) >> 1;
		build(ind*2 , l , mid);
		build(ind*2+1 , mid+1 , r);
		tree[ind].second = tree[ind*2].second;
	}
	void push(int ind , int l , int r){
		if(lzt[ind] != 0){
			tree[ind].first += lzt[ind];
			if(l != r){
				lzt[ind*2] += lzt[ind];
				lzt[ind*2 + 1] += lzt[ind];
			}
			lzt[ind] = 0;
		}
	}
	void update(int ind , int l , int r, int ql , int qr , int qv){
		push(ind,l,r);
		if(l >= ql and r <= qr){
			lzt[ind] += qv;
			push(ind,l,r);
			return;
		}
		else if(l > qr or r < ql){
			return;
		}
		else{
			int mid = (l + r) >> 1;
			update(ind*2 , l , mid , ql , qr , qv);
			update(ind*2+1 , mid+1 , r , ql , qr , qv);
			tree[ind] = min(tree[ind*2] , tree[ind*2+1]);
		}
	}
	void update(int l , int r , int v){
		update(1,0,tree_size,l,r,v);
	}
	pair < int , int > query(int ind , int l , int r , int ql , int qr){
		push(ind,l,r);
		if(l >= ql and r <= qr){
			return tree[ind];
		}
		else if(l > qr or r < ql){
			return {inf,inf};
		}
		else{
			int mid = (l + r) >> 1;
			return min(query(ind*2 , l , mid , ql , qr) , query(ind*2+1 , mid+1 , r , ql , qr));
		}
	}
	pair < int , int > query(int l , int r){
		auto ret = query(1,0,tree_size,l,r);
		ret.second *= is_inverse ? -1 : 1;
		return ret;
	}
};
void solve(){
	int n;
	cin >> n;
	string str;
	cin >> str;
	SEGT prefix(n,0) , suffix(n,1);
	int cur_sum = 0;
	for(int i = 0;i<n;i++){
		if(str[i] == 'C')cur_sum++;
		else cur_sum--;
		prefix.update(i+1 , i+1 , cur_sum);
	}
	cur_sum = 0;
	for(int i = n-1;i>=0;i--){
		if(str[i] == 'C')cur_sum++;
		else cur_sum--;
		suffix.update(i+1 , i+1 , cur_sum);
	}
	// cout << "pre : ";for(int i = 0;i<=12;i++)cout << prefix.query(i,i).first << " ";cout << endl;
	// cout << "suf : ";for(int i = 0;i<=12;i++)cout << suffix.query(i,i).first << " ";cout << endl;
	int q;
	cin >> q;
	while(q--){
		int l,r;
		cin >> l >> r;
		int tmp1 = -prefix.query(l-1,l-1).first , tmp2 = -suffix.query(r+1,r+1).first;
		prefix.update(l,r,tmp1);
		suffix.update(l,r,tmp2);
		// cout << "pre : ";for(int i = 0;i<=12;i++)cout << prefix.query(i,i).first << " ";cout << endl;
		// cout << "suf : ";for(int i = 0;i<=12;i++)cout << suffix.query(i,i).first << " ";cout << endl;
		//updates
		pair < int , int > qp = prefix.query(l,r) , qs = suffix.query(l,r);
		int local_ans = max(0,-qp.first) + max(0,-qs.first);
		int intersect = 0;
		if(qp.second >= qs.second){
			intersect = max(0,-qp.first) - max(0 , -prefix.query(qs.first , qs.first).first);
		}
		// cout << "local_ans : " << local_ans << endl;
		// cout << "intersect : " << intersect << endl;
		cout << local_ans - intersect << endl;
		//redo the updates
		prefix.update(l,r,-tmp1);
		suffix.update(l,r,-tmp2);
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18