제출 #170465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
170465		Retro3014	Election (BOI18_election)	C++17	0 / 100	5 ms	504 KiB

election

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e7;
const ll INFLL = 1e18;
const int MAX_N = 500000;

int N;
string str;
int Q;
bool chk[MAX_N+1];
int sum[MAX_N+1];

struct SEG{
	struct NODE{
		int l, r;
		pii mx, mn;
	};
	vector<NODE> seg;
	void add(){
		seg.pb({-1, -1, {-MAX_N-1, 0}, {MAX_N+1, 0}});
	}
	int SZ;
	void Init(int x){
		SZ = x;
		add();
		init(0, 1, SZ);
	}
	void init(int idx, int s, int e){
		if(s==e){
			seg[idx].mx = {sum[s], s};
			seg[idx].mn = {sum[s], s};
			return;
		}
		seg[idx].l = seg.size(); add(); seg[idx].r = seg.size(); add();
		init(seg[idx].l, s, (s+e)/2);
		init(seg[idx].r, (s+e)/2+1, e);
		seg[idx].mx = max(seg[seg[idx].l].mx, seg[seg[idx].r].mx);
		seg[idx].mn = min(seg[seg[idx].l].mn, seg[seg[idx].r].mn);
	}
	pii Mx(int x, int y){
		return mx(0, 1, SZ, x, y);
	}
	pii mx(int idx, int s, int e, int x, int y){
		if(x<=s && e<=y){
			return seg[idx].mx;
		}
		if(x>e || y<s){
			return {-INF, 0};
		}
		return max(mx(seg[idx].l, s, (s+e)/2, x, y), mx(seg[idx].r, (s+e)/2+1, e, x, y));
	}
	pii Mn(int x, int y){
		return mn(0, 1, SZ, x, y);
	}
	pii mn(int idx, int s, int e, int x, int y){
		if(x<=s && e<=y){
			return seg[idx].mn;
		}
		if(x>e || y<s){
			return {INF, 0};
		}
		return min(mn(seg[idx].l, s, (s+e)/2, x, y), mn(seg[idx].r, (s+e)/2+1, e, x, y));
	}
}Seg;

int main(){
	cin>>N>>str>>Q;
	for(int i=1; i<=N; i++){
		sum[i] = sum[i-1];
		if(str[i-1]=='C') sum[i]++;
		else	sum[i]--;
		//cout<<sum[i]<<endl;
	}
	Seg.Init(N);
	for(int i=0; i<Q; i++){
		int a, b;
		scanf("%d%d", &a, &b); a--;
		int s = sum[a], e = sum[b];
		pii mx = Seg.Mx(a+1, b), mn = Seg.Mn(a+1, b);
		//cout<<mx.first<<" "<<mx.second<<" "<<mn.first<<" "<<mn.second<<endl;
		if(mn.second<mx.second){
			printf("%d\n", max(0, s-mn.first) + max(0, mx.first-e));
		}else{
			pii mx2 = Seg.Mx(mn.second, b), mn2 = Seg.Mn(a+1, mx.second);
			mn2.first = min(mn2.first, s); mx2.first = max(mx2.first, e);
			//cout<<mn2.first<<" "<<mx2.first<<endl;
			printf("%d\n", s-mn2.first + mx2.first-e + max(mn2.first-mn.first, mx.first-mx2.first));
		}
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

election.cpp: In function 'int main()':
election.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b); a--;
   ~~~~~^~~~~~~~~~~~~~~~

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