oj.uz

답안 #171754

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171754 2019-12-30T09:55:48 Z dndhk Election (BOI18_election) C++14
100 / 100
 1700 ms 150232 KB 
#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 = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 500010;
const int MAX_K = 20;

int N, Q;
string str;
int d[MAX_N+1];

struct S{
	int idx, mx, cnt;
};
S nxt[MAX_N+1][MAX_K+1];

struct SEG{
	struct NODE{
		int l, r;
		int mx;
	};
	int SZ;
	vector<NODE> seg;
	void add(){
		seg.pb({-1, -1, -INF});
	}
	void Init(int x){
		SZ = x;
		add();
		init(0, 0, SZ);
	}
	void init(int idx, int s, int e){
		if(s==e)	{
			seg[idx].mx = d[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);
	}
	int Mx(int x, int y){
		return mx(0, 0, SZ, x, y);
	}
	int 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;
		return max(mx(seg[idx].l, s, (s+e)/2, x, y), mx(seg[idx].r, (s+e)/2+1, e, x, y));
	}
}Seg;

vector<int> st;

int main(){
	scanf("%d", &N);
	cin>>str;
	str.pb('0');
	for(int i=str.size(); i>0; i--){
		str[i] = str[i-1];
	}
	for(int i=1; i<=N; i++){
		d[i] = d[i-1];
		if(str[i]=='C')	d[i]++;
		else	d[i]--;
	}
	for(int i=0; i<MAX_K; i++)	nxt[N+1][i].idx = N+1;
	Seg.Init(N);
	for(int i=N; i>=0; i--){
		while(!st.empty() && d[st.back()]>d[i])	st.pop_back();
		if(st.empty()){
			nxt[i][0].idx = N+1;
			nxt[i][0].mx = nxt[i][0].cnt = 0;
		}else{
			if(d[st.back()]==d[i]){
				nxt[i][0].idx = st.back();
				nxt[i][0].mx = Seg.Mx(i, st.back()) - d[i];
				nxt[i][0].cnt = 0;
				st.pop_back();
			}else{
				nxt[i][0].idx = st.back();
				nxt[i][0].mx = 0;
				nxt[i][0].cnt = 1;
			}
		}
		for(int j=1; j<MAX_K; j++){
			nxt[i][j].idx = nxt[nxt[i][j-1].idx][j-1].idx;
			nxt[i][j].mx = max(nxt[i][j-1].mx, nxt[nxt[i][j-1].idx][j-1].mx);
			nxt[i][j].cnt = nxt[i][j-1].cnt + nxt[nxt[i][j-1].idx][j-1].cnt;
		}
		st.push_back(i);
	}
	scanf("%d", &Q);
	int t, dh, ans;
	while(Q--){
		int a, b; scanf("%d%d", &a, &b); a--;
		t = a, dh = 0, ans = 0;
		for(int i=MAX_K-1; i>=0; i--){
			if(nxt[t][i].idx<=b){
				ans+=nxt[t][i].cnt;
				dh = max(dh, nxt[t][i].mx);
				t = nxt[t][i].idx;
			}
		}
		dh = max(dh, Seg.Mx(t, b) - d[t]);
		dh -= (d[b] - d[t]);
		ans += max(0, dh);
		printf("%d\n", ans);
	}

	return 0;
}

Compilation message

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

Subtask #1
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1016 KB Output is correct
2 Correct 5 ms 1016 KB Output is correct
3 Correct 5 ms 1016 KB Output is correct
4 Correct 5 ms 888 KB Output is correct
5 Correct 5 ms 888 KB Output is correct

Subtask #2
54.0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1016 KB Output is correct
2 Correct 5 ms 1016 KB Output is correct
3 Correct 5 ms 1016 KB Output is correct
4 Correct 5 ms 888 KB Output is correct
5 Correct 5 ms 888 KB Output is correct
6 Correct 142 ms 20564 KB Output is correct
7 Correct 110 ms 20492 KB Output is correct
8 Correct 121 ms 20384 KB Output is correct
9 Correct 118 ms 20396 KB Output is correct
10 Correct 131 ms 20356 KB Output is correct
11 Correct 144 ms 20520 KB Output is correct
12 Correct 132 ms 20512 KB Output is correct
13 Correct 140 ms 20660 KB Output is correct
14 Correct 128 ms 20604 KB Output is correct
15 Correct 130 ms 20516 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1016 KB Output is correct
2 Correct 5 ms 1016 KB Output is correct
3 Correct 5 ms 1016 KB Output is correct
4 Correct 5 ms 888 KB Output is correct
5 Correct 5 ms 888 KB Output is correct
6 Correct 142 ms 20564 KB Output is correct
7 Correct 110 ms 20492 KB Output is correct
8 Correct 121 ms 20384 KB Output is correct
9 Correct 118 ms 20396 KB Output is correct
10 Correct 131 ms 20356 KB Output is correct
11 Correct 144 ms 20520 KB Output is correct
12 Correct 132 ms 20512 KB Output is correct
13 Correct 140 ms 20660 KB Output is correct
14 Correct 128 ms 20604 KB Output is correct
15 Correct 130 ms 20516 KB Output is correct
16 Correct 1072 ms 140772 KB Output is correct
17 Correct 898 ms 147848 KB Output is correct
18 Correct 944 ms 148240 KB Output is correct
19 Correct 988 ms 147584 KB Output is correct
20 Correct 1257 ms 147472 KB Output is correct
21 Correct 1700 ms 149284 KB Output is correct
22 Correct 1358 ms 149200 KB Output is correct
23 Correct 1409 ms 150232 KB Output is correct
24 Correct 1487 ms 149004 KB Output is correct
25 Correct 1222 ms 148520 KB Output is correct