oj.uz

답안 #319361

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
319361 2020-11-05T02:22:03 Z rqi Election (BOI18_election) C++14
0 / 100
 66 ms 65128 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define pb push_back
#define bk back()

const int MOD = 1000000007;

struct SegTree{
	const static int SZ = 524288;
	int mn[2*SZ];
	int lazy[2*SZ];
	void init(){
		for(int i = 1; i < 2*SZ; i++){
			mn[i] = 0;
			lazy[i] = 0;
		}
	}
	void pull(int ind){
		mn[ind] = min(mn[2*ind], mn[2*ind+1]);
	}
	void push(int ind){
		mn[ind]+=lazy[ind];
		if(ind < SZ){
			lazy[2*ind]+=lazy[ind];
			lazy[2*ind+1]+=lazy[ind];
		}
		lazy[ind] = 0;
	}
	void upd(int lo, int hi, int val, int ind = 1, int L = 0, int R = SZ-1){
		push(ind);
		if(R < lo || L > hi) return;
		
		if(lo <= L && R <= hi){
			lazy[ind]+=val;
			push(ind);
			//cout << ind << " " << L << " " << R << " " << mn[ind] << "\n";
			return;
		}

		int M = (L+R)/2;

		upd(lo, hi, val, 2*ind, L, M);
		upd(lo, hi, val, 2*ind+1, M+1, R);

		pull(ind);
	}
	int query(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1){
		push(ind);
		if(R < lo || L > hi) return MOD;
		
		if(lo <= L && R <= hi){
			// cout << "L,R,mn: " << L << " " << R << " " << mn[ind] << " " << lazy[ind] << "\n";
			// if(ind < SZ){
			// 	cout << mn[2*ind] << " " << lazy[2*ind] << "\n";
			// }
			return mn[ind];
		}

		int M = (L+R)/2;

		int Q1 = query(lo, hi, 2*ind, L, M);
		int Q2 = query(lo, hi, 2*ind+1, M+1, R);

		return min(Q1, Q2);
	}
};

const int mx = 500005;

int bt[mx]; //keep track of removed stuff
void upd(int ind, int val){
	assert(1 <= ind && ind < mx);
	while(ind < mx){
		bt[ind]+=val;
		ind+=ind&-ind;
	}
}

int sum(int ind){
	assert(0 <= ind && ind < mx);
	if(ind == 0) return 0;
	int res = 0;
	while(ind > 0){
		res+=bt[ind];
		ind-=ind&-ind;
	}
	return res;
}

int query(int l, int r){
	return sum(r)-sum(l-1);
}

int N;
string votes;
int Q;
int L[mx];
int R[mx];
int ans[mx];
SegTree seg;

int pref[mx];

vi npos[2*mx]; //positions of x+1 --> x, shifted by mx. back is current

void INSERT(int ind){ //removing T at position ind
	//cout << "INSERT " << ind << "\n";
	upd(ind, 1);
	seg.upd(1, ind, 1);
}

int QUERY(int l, int r){
	//cout << "QUERY: " << l << " " << r << "\n";
	int ans = query(l, r);
	//cout << "origans: " << ans << "\n";
	int ival = seg.query(r+1, r+1);
	int mval = seg.query(l, r+1);

	//if(l == 4 && r == 9){
		// for(int i = 1; i <= 12; i++){
		// 	cout << seg.query(i, i) << " ";
		// }
		// cout << "\n";
		//cout << ival << " " << mval << "\n";
	//}

	return ans+ival-mval;
}

int main(){
	cin >> N;
	cin >> votes;
	votes = "?" + votes;
	cin >> Q;
	for(int i = 1; i <= Q; i++){
		cin >> L[i] >> R[i];
	}
	seg.init();
	vpi queries;
	for(int i = 1; i <= Q; i++){
		queries.pb(mp(L[i], i));
	}
	sort(all(queries));

	pref[1] = 0;
	for(int i = 2; i <= N+1; i++){
		pref[i] = pref[i-1];
		if(votes[i-1] == 'C'){
			pref[i]++;
		}
		else{
			pref[i]--;
		}
	}

	for(int i = N; i >= 1; i--){
		if(votes[i] == 'T'){
			//cout << "i, pref[i+1] " << i << " " << pref[i+1] << "\n";
			npos[pref[i+1]+mx].pb(i);
		}
	}

	for(int i = -1; i >= -N; i--){
		if(sz(npos[i+mx])){
			//cout << i << " " << npos[i+mx].bk << "\n";
			INSERT(npos[i+mx].bk);
		}
	}

	int cursum = 0;
	for(int i = N+1; i >= 1; i--){
		if(i != N+1){
			if(votes[i] == 'C'){
				cursum++;
			}
			else if(votes[i] == 'T'){
				cursum--;
			}
		}
		seg.upd(i, i, cursum);
	}



	int curL = 1;
	
	for(int q = 0; q < Q; q++){
		int qind = queries[q].s;

		//cout << "qind: " << qind << "\n";

		while(curL < L[qind]){
			if(votes[curL] == 'C'){
				if(sz(npos[pref[curL+1]-1+mx])){
					INSERT(npos[pref[curL+1]-1+mx].bk);
				}
			}
			else if(votes[curL] == 'T'){
				npos[pref[curL]+mx].pop_back();
				//ERASE(npos[pref[curL]+mx].bk); doesn't seem necessary?
			}
			curL++;
		}

		ans[qind] = QUERY(L[qind], R[qind]);
	}

	for(int i = 1; i <= Q; i++){
		cout << ans[i] << "\n";
	}
}

Subtask #1
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 66 ms 65128 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 66 ms 65128 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 66 ms 65128 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -