oj.uz

답안 #848174

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
848174 2023-09-11T14:00:29 Z KN200711 Election (BOI18_election) C++14
0 / 100
 7 ms 27480 KB 
# include <bits/stdc++.h>
# define fi first
# define se second
using namespace std;

vector< pair<int, int> > pref[500001], suff[500001];
int ans[500001];
int N;
string S;

int seg[2000001];

void build(int lf, int rg, int nd) {
	seg[nd] = 0;
	if(lf == rg) return;
	int mid = (lf + rg)/2;
	build(lf, mid, 2*nd+1);
	build(mid+1, rg, 2*nd+2);
}

void upd(int lf, int rg, int nd, int clf, int crg) {
	if(clf > rg || lf > crg) return;
	if(clf <= lf && rg <= crg) seg[nd]++;
	else {
		int mid = (lf + rg) / 2;
		upd(lf, mid, 2*nd+1, clf, crg);
		upd(mid+1, rg, 2*nd+2, clf, crg);
	}
}

int qry(int lf, int rg, int nd, int pos) {
	if(lf == rg) return seg[nd];
	else {
		int mid = (lf + rg) / 2;
		seg[2*nd+1] += seg[nd];
		seg[2*nd+2] += seg[nd];
		seg[nd] = 0;
		if(pos <= mid) return qry(lf, mid, 2*nd+1, pos);
		else return qry(mid+1, rg, 2*nd+2, pos);
	}
}

void calc() {
	vector< pair<int, int> > L, V;
	L.clear();
	V.clear();
	build(0, N-1, 0);
	for(int i=0;i<N;i++) {
	//	cout<<i<<endl;
		if(V.size() == 0) V.push_back(make_pair(i, i));
		else V.back().se++;
		
		if(S[i] == 'C') {
			if(V.size() == 0) {
				L.back().se++;
			} else {
				L.push_back(V.back());
				L.push_back(make_pair(-1, 1));
				V.clear();
			}
		} else {
			if(V.size() == 1) upd(0, N-1, 0, V.back().fi, V.back().se);
		//	if(V.size() > 0) cout<<i<<" "<<V.back().fi<<" "<<V.back().se<<endl;
			if(L.size() && L.back().se == 1) {
				L.pop_back();
				if(V.size() == 0) V.push_back(L.back());
				else V.back().fi = L.back().fi;
				
				L.pop_back();
			} else if(L.size()) L.back().se--;
		}
		
		
		for(int k=0;k<pref[i].size();k++) {
		//	cout<<"qry : "<<pref[i][k].se<<" "<<pref[i][k].fi<<endl;
			ans[pref[i][k].se] = max(ans[pref[i][k].se], qry(0, N-1, 0, pref[i][k].fi));
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>N;
	cin>>S;
	
	int Q;
	cin>>Q;
	for(int tc = 1;tc<=Q;tc++) {
		int a, b;
		cin>>a>>b;
		if(a > b) swap(a, b);
		a--;
		b--;
		pref[b].push_back(make_pair(a, tc));
		suff[a].push_back(make_pair(b, tc));
	}
	
	
	// calculate prefnya dulu
	calc();
	
	string T = "";
	for(int i=N-1;i>=0;i--) T += S[i];
	S = T;
	for(int i=0;i<N;i++) pref[i].clear();
	for(int i=N-1;i>=0;i--) {
		for(int k=0;k<suff[i].size();k++) {
			pref[N - i - 1].push_back(make_pair(N - suff[i][k].fi - 1, suff[i][k].se));
		}
	}
	
	calc();
	for(int i=1;i<=Q;i++) cout<<ans[i]<<"\n";
	return 0;
}

Compilation message

election.cpp: In function 'void calc()':
election.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int k=0;k<pref[i].size();k++) {
      |               ~^~~~~~~~~~~~~~~
election.cpp: In function 'int main()':
election.cpp:109:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for(int k=0;k<suff[i].size();k++) {
      |               ~^~~~~~~~~~~~~~~

Subtask #1
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 27480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 27480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 27480 KB Output isn't correct
2 Halted 0 ms 0 KB -