Submission #1138852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138852		dadas08	Election (BOI18_election)	C++20	0 / 100	1 ms	576 KiB

election

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
// #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
void _main();
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	_main();
	return 0;
}
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vl = std::vector<ll>;
using vii = std::vector<pair<int, int> >;
using vvl = std::vector<vl>;
using vll = std::vector<pair<ll , ll> >;
using vd = std::vector<double>;
using vvd = std::vector<vd>;
using vs = std::vector<std::string>;
using vvs = std::vector<vs>;
using vb = std::vector<bool>;
using vvb = std::vector<vb>;
using vc = std::vector<char>;
using vvc = std::vector<vc>;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using piil = std::pair<pair<int, int>, ll>;
using mii = std::map<int, int>;
using mll = std::map<ll, ll>;
using pql = std::priority_queue<ll>;
using pqi = std::priority_queue<int>;
using pqiil = std::priority_queue<pair<pair<int, int>, ll> >;
using pqii = std::priority_queue<pair<int, int> >;

#define pb push_back
#define ps push
#define eb emplace_back
#define is insert
#define er erase
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define sf(i) sizeof(i)
#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define rep(i, L, R) for(ll i = L;i<=R;i++)
#define pcis precision
#define sz(a) ((ll) a.size())

template<typename T>
struct infinity {
	static constexpr T max=std::numeric_limits<T>::max();
	static constexpr T min=std::numeric_limits<T>::min();
	static constexpr T value=std::numeric_limits<T>::max()/2;
	static constexpr T mvalue=std::numeric_limits<T>::min()/2;
};
template<typename T>constexpr T INF=infinity<T>::value;
constexpr ll lINF=INF<ll>;
constexpr int iINF = INF<int>;
constexpr ld PI = 3.1415926535897932384626;

#define unit ll
#define RANGE_OUT -lINF

unit tree[1000001 * 4];
unit lazy[1000001 * 4];

unit F(unit a, unit b) {
	return max(a, b);
}

unit init(unit A[], int node, int start, int end) {
	if(start == end) return tree[node] = A[start];
	int mid = (start + end) / 2;
	return tree[node] = F(init(A, node*2, start, mid) , init(A, node*2+1, mid+1, end));
}

void overlap(int node, unit diff) {
	lazy[node] = lazy[node] + diff;
}

void update_lazy(int node, int start, int end) {
	if(lazy[node]) {
		tree[node] = tree[node] + (lazy[node] * (end - start +1));
		if(start != end) {
			overlap(node*2, lazy[node]);
			overlap(node*2 + 1, lazy[node]);
		}
		lazy[node] = 0;
	}
}

unit get(int node, int start, int end, int left, int right) {
	update_lazy(node, start, end);
	if(right < start || left > end) return RANGE_OUT;
	if(left <= start && end <= right) return tree[node];
	int mid = (start + end) / 2;
	return F(get(node*2, start, mid, left, right) , get(node*2+1, mid+1, end, left, right));
}

void update(int node, int start, int end, int left, int right, unit diff) {
	update_lazy(node, start, end);
	if(right < start || left > end) return;
	if(left <= start && end <= right) {
		overlap(node, diff);
		update_lazy(node, start, end);
		return;
	}

	int mid = (start + end) / 2;
	update(node*2, start, mid, left, right, diff);
	update(node*2+1, mid+1, end, left, right, diff);
	tree[node] = F(tree[node*2] , tree[node*2+1]);
}

void _main() {

	ll N;
	cin >> N;
	string SS;
	cin >> SS;
	ll A[N+1];

	rep(i,1,N) {
		A[i] = (SS[i-1] == 'C'?1:-1);
	}

	ll Q;
	cin >> Q;
	pll query[Q+1];
	rep(i,1,Q) cin >> query[i].f >> query[i].s;


	ll S[N+1];
	S[0] = 0;
	rep(i,1,N) S[i] = S[i-1] + A[i];

	stack<pll> stk;
	stk.ps({-lINF, N+1});

	ll to[N+1];
	memset(to, 0 ,sf(to));

	for (ll i = N; i>=0; i--) {
		while (stk.top().f >= S[i]) stk.pop();
		to[i] = stk.top().s;
		stk.ps({i, S[i]});
	}

	init(S, 1, 1, N);

	vl adj[N+2];
	rep(i,0,N) adj[to[i]].pb(i);

	vll qry[N+2];
	rep(i,1,Q) {
		auto [l ,r] = query[i];
		qry[l-1].pb({r, i});
	}

	ll RES[Q+1];

	function<void(ll, ll)> DFS = [&](ll node, ll dep) -> void {
//		cout << "goto" << node << endl;
		for (auto [r, idx] : qry[node]) {
			RES[idx] = dep + (max((ll) (node == 0?0:-lINF), (ll)get(1, 1, N, max(node, (ll)1), r)) - get(1, 1, N, r, r));
		}
		for (auto i : adj[node]) {
			if (node != N+1) update(1, 1, N, node, N, 1);// node 바로 전에서 +를 때려버림
			DFS(i, dep+1);
			if (node != N+1) update(1, 1, N, node, N, -1);
		}
//		cout << "ret" << node << endl;
		return;
	};

	DFS(N+1, -1);
	rep(i,1,Q) cout << RES[i] << endl;
}

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