oj.uz

답안 #171752

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171752 2019-12-30T09:53:39 Z dndhk Election (BOI18_election) C++14
82 / 100
 1134 ms 148360 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 = 500000;
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);
	while(Q--){
		int a, b; scanf("%d%d", &a, &b); a--;
		int 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:117: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 888 KB Output is correct
4 Correct 5 ms 1016 KB Output is correct
5 Correct 5 ms 1016 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 888 KB Output is correct
4 Correct 5 ms 1016 KB Output is correct
5 Correct 5 ms 1016 KB Output is correct
6 Correct 125 ms 21092 KB Output is correct
7 Correct 110 ms 21108 KB Output is correct
8 Correct 111 ms 21028 KB Output is correct
9 Correct 119 ms 21024 KB Output is correct
10 Correct 146 ms 21172 KB Output is correct
11 Correct 146 ms 21092 KB Output is correct
12 Correct 134 ms 21212 KB Output is correct
13 Correct 142 ms 21256 KB Output is correct
14 Correct 135 ms 21160 KB Output is correct
15 Correct 126 ms 21100 KB Output is correct

Subtask #3
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 888 KB Output is correct
4 Correct 5 ms 1016 KB Output is correct
5 Correct 5 ms 1016 KB Output is correct
6 Correct 125 ms 21092 KB Output is correct
7 Correct 110 ms 21108 KB Output is correct
8 Correct 111 ms 21028 KB Output is correct
9 Correct 119 ms 21024 KB Output is correct
10 Correct 146 ms 21172 KB Output is correct
11 Correct 146 ms 21092 KB Output is correct
12 Correct 134 ms 21212 KB Output is correct
13 Correct 142 ms 21256 KB Output is correct
14 Correct 135 ms 21160 KB Output is correct
15 Correct 126 ms 21100 KB Output is correct
16 Incorrect 1134 ms 148360 KB Output isn't correct
17 Halted 0 ms 0 KB -