oj.uz

Submission #548286

# Submission time Handle Problem Language Result Execution time Memory
548286 2022-04-12T21:24:25 Z Bungmint Election (BOI18_election) C++17
100 / 100
 500 ms 52172 KB 
//Copyright © 2022 Youngmin Park. All rights reserved.
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vpi = vector<pii>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
template <typename T, size_t SZ>
using ar = array<T, SZ>;

#define all(v) (v).begin(), (v).end()
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define REP(a) F0R(_, a)

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7; //998244353;
const ld PI = acos((ld)-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
    return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v)
{
    os << '{';
    string sep;
    for (const T &x : v)
        os << sep << x, sep = ", ";
    return os << '}';
}
void dbg_out()
{
    cerr << endl;
}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
    cerr << ' ' << H;
    dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

inline namespace RecursiveLambda{
	template <typename Fun>
	struct y_combinator_result{
		Fun fun_;
		template <typename T> 
		explicit y_combinator_result(T &&fun): fun_(forward<T>(fun)){}
		template <typename...Args>
		decltype(auto) operator()(Args &&...args){
			return fun_(ref(*this), forward<Args>(args)...);
		}
	};
	template <typename Fun>
	decltype(auto) y_combinator(Fun &&fun){
		return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
	}
};

void setIO(string s) // USACO
{
	#ifndef LOCAL
	    freopen((s + ".in").c_str(), "r", stdin);
	    freopen((s + ".out").c_str(), "w", stdout);
	#endif
}

const int N = 5e5;
int str[N];
struct Node {
	bool isConst;
	int pref, suf, sum, mi;
	Node() {
		isConst = 1;
	}
	Node(int x) {
		isConst = 0;
		pref = max(x, 0);
		suf = max(x, 0);
		sum = x;
		mi = max(0, pref);
	}
	friend Node merge(const Node& a, const Node& b) {
		if (a.isConst) return b;
		if (b.isConst) return a;
		Node res{};
		res.isConst = 0;
		res.pref = max(a.pref, b.pref + a.sum);
		res.suf = max(b.suf, a.suf + b.sum);
		res.sum = a.sum + b.sum;
		res.mi = max(a.pref + b.suf, max(a.mi + b.sum, b.mi + a.sum));
		return res;
	}
}t[N * 4];
int n, q, SZ = 1;

void init() {
	while (SZ < n) SZ *= 2;
}
void build(int x = 0, int l = 0, int r = SZ) {
	if (r - l == 1) {
		if (l < n) t[x] = Node(str[l]);
		return;
	}
	int m = (l + r) >> 1;
	build(2 * x + 1, l, m);
	build(2 * x + 2, m, r);
	t[x] = merge(t[2 * x + 1], t[2 * x + 2]);
}
Node query(int l, int r, int x = 0, int lx = 0, int rx = SZ) {
	if (lx >= r || rx <= l) return Node();
	if (l <= lx && rx <= r) return t[x];
	int m = (lx + rx) >> 1;
	Node a = query(l, r, 2 * x + 1, lx, m);
	Node b = query(l, r, 2 * x + 2, m, rx);
	return merge(a, b);
}

void solve()
{
	cin >> n;
	F0R(i, n) {
		char c;
		cin >> c;
		if (c == 'C') str[i] = -1;
		else str[i] = 1;
	}
	cin >> q;
	init();
	build();
	REP(q) {
		int l, r;
		cin >> l >> r;
		l--;
		Node z = query(l, r);
		cout << z.mi << '\n';
	}
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int testcase=1;
    // cin >> testcase;
    while (testcase--)
    {
        solve();
    }
}

Compilation message

election.cpp: In function 'void setIO(std::string)':
election.cpp:94:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |      freopen((s + ".in").c_str(), "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:95:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |      freopen((s + ".out").c_str(), "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 39508 KB Output is correct
2 Correct 18 ms 39488 KB Output is correct
3 Correct 18 ms 39516 KB Output is correct
4 Correct 17 ms 39480 KB Output is correct
5 Correct 16 ms 39464 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 39508 KB Output is correct
2 Correct 18 ms 39488 KB Output is correct
3 Correct 18 ms 39516 KB Output is correct
4 Correct 17 ms 39480 KB Output is correct
5 Correct 16 ms 39464 KB Output is correct
6 Correct 65 ms 40908 KB Output is correct
7 Correct 62 ms 40808 KB Output is correct
8 Correct 76 ms 40752 KB Output is correct
9 Correct 59 ms 40752 KB Output is correct
10 Correct 63 ms 40732 KB Output is correct
11 Correct 62 ms 41008 KB Output is correct
12 Correct 65 ms 41024 KB Output is correct
13 Correct 76 ms 40916 KB Output is correct
14 Correct 63 ms 40932 KB Output is correct
15 Correct 62 ms 40836 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 39508 KB Output is correct
2 Correct 18 ms 39488 KB Output is correct
3 Correct 18 ms 39516 KB Output is correct
4 Correct 17 ms 39480 KB Output is correct
5 Correct 16 ms 39464 KB Output is correct
6 Correct 65 ms 40908 KB Output is correct
7 Correct 62 ms 40808 KB Output is correct
8 Correct 76 ms 40752 KB Output is correct
9 Correct 59 ms 40752 KB Output is correct
10 Correct 63 ms 40732 KB Output is correct
11 Correct 62 ms 41008 KB Output is correct
12 Correct 65 ms 41024 KB Output is correct
13 Correct 76 ms 40916 KB Output is correct
14 Correct 63 ms 40932 KB Output is correct
15 Correct 62 ms 40836 KB Output is correct
16 Correct 500 ms 50964 KB Output is correct
17 Correct 464 ms 50620 KB Output is correct
18 Correct 441 ms 50888 KB Output is correct
19 Correct 380 ms 50340 KB Output is correct
20 Correct 448 ms 50124 KB Output is correct
21 Correct 460 ms 51980 KB Output is correct
22 Correct 466 ms 51944 KB Output is correct
23 Correct 458 ms 52172 KB Output is correct
24 Correct 460 ms 51708 KB Output is correct
25 Correct 461 ms 51336 KB Output is correct