oj.uz

답안 #254142

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
254142 2020-07-29T12:01:01 Z amoo_safar Election (BOI18_election) C++14
100 / 100
 928 ms 39700 KB 
// Null
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 5e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

int n, q, ps[N];
str s;
int lz[N << 2], seg[N << 2];

void Apply(int id, int x){
	seg[id] += x;
	lz[id] += x;
}
void Shift(int id){
	Apply(id << 1, lz[id]);
	Apply(id << 1 | 1, lz[id]);
	lz[id] = 0;
}
void Add(int id, int l, int r, int x, int L, int R){
	if(r <= L || R <= l) return ;
	if(l <= L && R <= r){
		Apply(id, x);
		return ;
	}
	Shift(id);
	int mid = (L + R) >> 1;
	Add(id << 1, l, r, x, L, mid);
	Add(id << 1 | 1, l, r, x, mid, R);
	seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
}
int Get(int id, int l, int r, int L, int R){
	if(r <= L || R <= l) return 1e9;
	if(l <= L && R <= r) return seg[id];
	Shift(id);
	int mid = (L + R) >> 1;
	return min( Get(id << 1, l, r, L, mid), Get(id << 1 | 1, l, r, mid, R) );
}

int ans[N];
vector< pair<int, int> > Q[N], M;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> s >> q;
	int l, r;
	for(int i = 0; i < q; i++){
		cin >> l >> r;
		Q[l - 1].pb({r, i});
	}
	for(int i = 1; i <= n; i++) ps[i] = ps[i - 1] + (s[i - 1] == 'T' ? 1 : -1);
	
	//for(int i = 0; i <= n; i++) cerr << ps[i] << ' ';
	//cerr << "\n\n";

	int Sm, X, Y;
	for(int i = n; i >= 0; i--){
		//Add(1, i, i + 1, ps[i], 0, n + 1);
		int la = i;
		while(!M.empty()){
			if(M.back().F > ps[i]) break;
			Add(1, la + 1, M.back().S + 1, M.back().F - ps[i], 0, n + 1);
			la = M.back().S;
			M.pop_back();
		}
		M.pb({ps[i], la});

		for(auto [r, qn] : Q[i]){
			Sm = ps[r] - ps[i];
			//debug(Get(1, r, r + 1, 0, n + 1));
			X = ps[r] - Get(1, r, r + 1, 0, n + 1) - ps[i];
			Y = (Sm - X) - Get(1, i, r + 1, 0, n + 1);

			ans[qn] = X + Y;
			//cerr << i + 1 << ' ' << r << " -> "<< Sm << ' ' << X << '\n';
		}
	}

	for(int i = 0; i < q; i++) cout << ans[i] << '\n';
	return 0;
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:83:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
   for(auto [r, qn] : Q[i]){
            ^

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12160 KB Output is correct
2 Correct 9 ms 12160 KB Output is correct
3 Correct 8 ms 12160 KB Output is correct
4 Correct 9 ms 12160 KB Output is correct
5 Correct 9 ms 12160 KB Output is correct
6 Correct 95 ms 16504 KB Output is correct
7 Correct 87 ms 16120 KB Output is correct
8 Correct 89 ms 16120 KB Output is correct
9 Correct 94 ms 16376 KB Output is correct
10 Correct 93 ms 16376 KB Output is correct
11 Correct 95 ms 16888 KB Output is correct
12 Correct 100 ms 16760 KB Output is correct
13 Correct 103 ms 16956 KB Output is correct
14 Correct 96 ms 16760 KB Output is correct
15 Correct 107 ms 16564 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12160 KB Output is correct
2 Correct 9 ms 12160 KB Output is correct
3 Correct 8 ms 12160 KB Output is correct
4 Correct 9 ms 12160 KB Output is correct
5 Correct 9 ms 12160 KB Output is correct
6 Correct 95 ms 16504 KB Output is correct
7 Correct 87 ms 16120 KB Output is correct
8 Correct 89 ms 16120 KB Output is correct
9 Correct 94 ms 16376 KB Output is correct
10 Correct 93 ms 16376 KB Output is correct
11 Correct 95 ms 16888 KB Output is correct
12 Correct 100 ms 16760 KB Output is correct
13 Correct 103 ms 16956 KB Output is correct
14 Correct 96 ms 16760 KB Output is correct
15 Correct 107 ms 16564 KB Output is correct
16 Correct 897 ms 37264 KB Output is correct
17 Correct 703 ms 33880 KB Output is correct
18 Correct 799 ms 34624 KB Output is correct
19 Correct 786 ms 36236 KB Output is correct
20 Correct 880 ms 36536 KB Output is correct
21 Correct 837 ms 39172 KB Output is correct
22 Correct 905 ms 38484 KB Output is correct
23 Correct 841 ms 39700 KB Output is correct
24 Correct 869 ms 38788 KB Output is correct
25 Correct 928 ms 37812 KB Output is correct