oj.uz

Submission #459610

# Submission time Handle Problem Language Result Execution time Memory
459610 2021-08-08T18:49:59 Z nkato Election (BOI18_election) C++17
100 / 100
 1452 ms 35764 KB 
#include <bits/stdc++.h>

using namespace std;

/////////////////////// MACROS ////////////////////////////////////////////
using ll = long long;
using ld = long double;
using db = double;
using str = string;

using pi = pair<int,int>;
using pl = pair<ll,ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;


#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcTU> using P = pair<T,U>;
tcT> using PR = pair<T,T>;
tcTU> using omap = unordered_map<T, U>;
tcT> using oset = unordered_set<T>;
tcT> using mset = multiset<T>;

#define mp make_pair
#define fi first
#define se second

#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define ppb pop_back()
#define pb push_back
#define eb emplace_back
#define pf push_front

#define lb lower_bound
#define ub upper_bound

// LOOPS
#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)
#define each(a,x) for (auto& a: x)

/////////////////////// IMPORANT VARS /////////////////////////////////////

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INFL = 1e18+10;
const int INF = 1e9+10;
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;
tcT> using pql = priority_queue<T,vector<T>,less<T>>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define nl '\n'


// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;

// tcT> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 
// #define ook order_of_key
// #define fbo find_by_order

// struct chash { 
// 	const uint64_t C = ll(2e18*PI)+71;
// 	const int RANDOM = rng();
// 	ll operator()(ll x) const {
// 		return __builtin_bswap64((x^RANDOM)*C); }
// };
// template<class K,class V> using um = unordered_map<K,V,chash>;
// template<class K,class V> using ht = gp_hash_table<K,V,chash>;
// template<class K,class V> V get(ht<K,V>& u, K x) {
// 	auto it = u.find(x); return it == end(u) ? 0 : it->s; }

tcT> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0; } 
tcT> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; }

/////////////////////// TO_STRING /////////////////////////////////////////
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) {
	#ifdef LOCAL
		return b ? "true" : "false";
	#else
		return ts((int)b);
	#endif
}
tcTU> str ts(pair<T,U> p) {
	#ifdef LOCAL
		return "("+ts(p.fi)+", "+ts(p.se)+")";
	#else
		return ts(p.fi)+" "+ts(p.se);
	#endif
}

tcTU> str ts(V<pair<T, U>> v) {
	#ifdef LOCAL
		bool fst = 1; str res = "{";
		for (const auto& x: v) {
			if (!fst) res += ", ";
			fst = 0; res += ts(x);
		}
		res += "}"; return res;
	#else
		bool fst = 1; str res = "";
		for (const auto& x: v) {
			if (!fst) res += " ";
			fst = 0; res += ts(x);
		}
		return res;
	#endif
}

tcT> str ts(T v) {
	#ifdef LOCAL
		bool fst = 1; str res = "{";
		for (const auto& x: v) {
			if (!fst) res += ", ";
			fst = 0; res += ts(x);
		}
		res += "}"; return res;
	#else
		bool fst = 1; str res = "";
		for (const auto& x: v) {
			if (!fst) res += " ";
			fst = 0; res += ts(x);
		}
		return res;

	#endif
}

///////////////////////// DEBUG ///////////////////////////////////////////
#define tcTUU tcT, class ...U
void DBG() { cerr << "]" << endl; }
tcTUU> void DBG(const T& t, const U&... u) {
	cerr << ts(t); if (sizeof...(u)) cerr << ", ";
	DBG(u...); }
#ifdef LOCAL
	#define _GLIBCXX_DEBUG
	#define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
	#define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
		 << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
#else
	#define dbg(...) 0
	#define chk(...) 0
#endif

///////////////////////// FILE I/O ////////////////////////////////////////
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
void setPrec() { cout << fixed << setprecision(15); }
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }
void setIO(str s = "") {
	unsyncIO(); setPrec();
	#ifndef LOCAL	
		if (sz(s)) setIn(s+".in"), setOut(s+".out"); // for USACO
	#endif
}

///////////////////////// TEMPLATE ABOVE //////////////////////////////////

// REMEMBER
// - Don't focus on only one approach
// - Read Problem Fully
// - Think of Edges Cases
// - Implement carefully

struct T {
	int pfx, sfx, tot, ans;

	T() {
		pfx = sfx = tot = ans = 0;
	}

	T(int p, int s, int t, int a) {
		pfx = p, sfx = s, tot = t, ans = a;
	}

	bool operator==(T a) {
		return (pfx == a.pfx && sfx == a.sfx
			 && tot == a.tot && ans == a.ans);
	}
};

struct Seg {
	V<T> seg; int N;
	const T ID = T();
	T comb(T a, T b) { 
		T c;

		c.tot = a.tot+b.tot;
		c.pfx = max(a.tot+b.pfx, a.pfx);
		c.sfx = max(b.tot+a.sfx, b.sfx);
		c.ans = max(max(a.ans+b.tot, b.ans+a.tot), a.pfx+b.sfx);
		return c;
	}

	void init(int _N) { N = 1; while(N < _N) N *= 2; seg.assign(2*N, ID); }

	void pull(int p) { seg[p] = comb(seg[2*p+1], seg[2*p+2]); }

	void build(const V<T>& A, int x, int lx, int rx) {
		if (rx-lx == 1) {
			if (lx < sz(A)) seg[x] = A[lx];
			return;
		}
		int m = (lx+rx)/2;
		build(A, x*2+1, lx, m);
		build(A, x*2+2, m, rx);
		pull(x);
	}

	void upd(int i, T v, int x, int lx, int rx) {
		if (rx-lx == 1) {
			seg[x] = v;
			return;
		}
		int m = (lx+rx)/2;
		if (i < m) upd(i, v, x*2+1, lx, m);
		else upd(i, v, x*2+2, m, rx);
		pull(x);
	}

	T qry(int l, int r, int x, int lx, int rx) {
		if (lx >= r || l >= rx) return ID;
		if (lx >= l && rx <= r) return seg[x];
		int m = (lx+rx)/2;
		T v1 = qry(l, r, 2*x+1, lx, m);
		T v2 = qry(l, r, 2*x+2, m, rx);
		return comb(v1, v2); 
	}
	
	void build(const V<T>& A) { build(A, 0, 0, N); }
	void upd(int i, T v) { upd(i, v, 0, 0, N); }
	T qry(int l, int r) { return qry(l, r, 0, 0, N); }
} st;

void solve() {
	int n; cin >> n;
	str s; cin >> s;
	V<T> a(n);
	F0R(i, n) {
		int v = (s[i] == 'C' ? -1 : 1);
		a[i] = T(max(0, v), max(0, v), v, max(0, v));
	}
	st.init(n);
	st.build(a);

	int q; cin >> q;
	rep(q) {
		int l, r; cin >> l >> r;
		--l;
		cout << st.qry(l, r).ans << endl;
	}
}

int main() {
	setIO(); 

	int TT = 1;
	// cin >> TT;

	rep(TT) solve();

	exit(0);
}

Compilation message

election.cpp: In function 'void setIn(str)':
election.cpp:171:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 | void setIn(str s) { freopen(s.c_str(),"r",stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
election.cpp: In function 'void setOut(str)':
election.cpp:172:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 | void setOut(str s) { freopen(s.c_str(),"w",stdout); }
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 324 KB Output is correct
2 Correct 5 ms 328 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 5 ms 324 KB Output is correct
5 Correct 5 ms 332 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 324 KB Output is correct
2 Correct 5 ms 328 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 5 ms 324 KB Output is correct
5 Correct 5 ms 332 KB Output is correct
6 Correct 163 ms 6876 KB Output is correct
7 Correct 160 ms 6860 KB Output is correct
8 Correct 166 ms 6844 KB Output is correct
9 Correct 159 ms 6816 KB Output is correct
10 Correct 164 ms 6776 KB Output is correct
11 Correct 173 ms 6984 KB Output is correct
12 Correct 183 ms 6976 KB Output is correct
13 Correct 167 ms 6980 KB Output is correct
14 Correct 163 ms 6972 KB Output is correct
15 Correct 197 ms 7000 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 324 KB Output is correct
2 Correct 5 ms 328 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 5 ms 324 KB Output is correct
5 Correct 5 ms 332 KB Output is correct
6 Correct 163 ms 6876 KB Output is correct
7 Correct 160 ms 6860 KB Output is correct
8 Correct 166 ms 6844 KB Output is correct
9 Correct 159 ms 6816 KB Output is correct
10 Correct 164 ms 6776 KB Output is correct
11 Correct 173 ms 6984 KB Output is correct
12 Correct 183 ms 6976 KB Output is correct
13 Correct 167 ms 6980 KB Output is correct
14 Correct 163 ms 6972 KB Output is correct
15 Correct 197 ms 7000 KB Output is correct
16 Correct 1341 ms 34816 KB Output is correct
17 Correct 1261 ms 34464 KB Output is correct
18 Correct 1335 ms 34676 KB Output is correct
19 Correct 1239 ms 34228 KB Output is correct
20 Correct 1348 ms 33904 KB Output is correct
21 Correct 1312 ms 35608 KB Output is correct
22 Correct 1330 ms 35620 KB Output is correct
23 Correct 1352 ms 35764 KB Output is correct
24 Correct 1452 ms 35480 KB Output is correct
25 Correct 1341 ms 34984 KB Output is correct