oj.uz

답안 #705070

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
705070 2023-03-03T10:47:53 Z Zflop Election (BOI18_election) C++14
100 / 100
 481 ms 44832 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
/*
ID: 10002181
LANG: C++
TASK: lamps
*/
 
using str = string; // yay python!
using ld = long double; // or double, if TL is tight
using ll = long long;
using int64 = ll;
using db = double;
using ull = unsigned long long;
 
#define ch() getchar()
#define pc(x) putchar(x)
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
using vi = V<int>;
using vb = V<bool>;
using vpi = V<pair<int,int>>;
using vvi = V<vi>;
using vl = V<ll>;
using vd = V<ld>;
using vstr = V<str>;
 
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rev(x) reverse(all(x))
#define sz(x) (int)(x).size()
#define rall(x) x.rbegin(), x.rend()
#define AR array
 
// loops
#define F0R(i, a, b) for (int i=a; i<b;++i)
#define FOR(i, a) for (int i=0; i<a;++i)
#define FORn(i, a) for (int i=1; i<=a;++i)
#define ROF(i,a) for(int i=a-1; i >= 0;--i)
#define R0F(i,a,b) for(int i=a; i > b;--i)
#define ROFn(i,a) for(int i=a; i > 0;--i)
#define rep(a) F0R(_, a)
#define trav(i,x) for(auto& i:x)
 
// pairs
#define mp make_pair
#define pi pair <int, int>
#define f first
#define s second
 
// vectors
#define lb lower_bound
#define ub upper_bound
#define SUM(v) accumulate(all(v), 0LL)
#define MN(v) *min_element(all(v))
#define MX(v) *max_element(all(v))
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define eb emplace_back
#define ft front()
#define bk back()
#define ins insert
#define pf push_front
#define pb push_back
#define emt empty()
#define rsz resize
 
#define pob pop_back()
#define pof pop_front()
 
#define swp(a,b) a^=b^=a^=b
 
#define ts to_string
 
#define setIO()  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
 
const ll MOD = 1e9+7;
const ll MAX = 100000000000;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
 
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
 
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
 
tcT> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; }
 
tcTU> T fstTrue(T lo, T hi, U f) {
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true
		T mid = lo+(hi-lo)/2;
		f(mid) ? hi = mid : lo = mid+1;
	}
	return lo;
}
tcTU> T lstTrue(T lo, T hi, U f) {
	lo --; assert(lo <= hi); // assuming f is decreasing
	while (lo < hi) { // find first index such that f is true
		T mid = lo+(hi-lo+1)/2;
		f(mid) ? lo = mid : hi = mid-1;
	}
	return lo;
}
 
//INPUT
#define tcTUU tcT, class ...U
tcT> void re(complex<T>& c);
tcTU> void re(pair<T,U>& p);
tcT> void re(V<T>& v);
tcT, size_t SZ> void re(AR<T,SZ>& a);
 
tcT> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
tcTUU> void re(T& t, U&... u) { re(t); re(u...); }
 
tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; }
tcTU> void re(pair<T,U>& p) { re(p.f,p.s); }
tcT> void re(V<T>& x) { trav(a,x) re(a); }
tcT> void rv(int n, V<T>& x) { x.rsz(n); re(x); }
 
//OUTPUT
namespace output {
	tcT> void PS(V<T>& x) { FOR(i,sz(x)) cout << x[i] << " \n"[i + 1 == sz(x)];}
	tcT> void PS(bool ok) { if(ok) cout << "YES\n"; else cout << "NO\n"; }
    template<class T1, class T2> void pr(const pair<T1,T2>& x);
    tcT, size_t SZ> void pr(const array<T,SZ>& x);
    tcT> void pr(const vector<T>& x);
    tcT> void pr(const set<T>& x);
    template<class T1, class T2> void pr(const map<T1,T2>& x);
 
    tcT> void pr(const T& x) { cout << x; }
    template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) {
        pr(first); pr(rest...);
    }
 
    template<class T1, class T2> void pr(const pair<T1,T2>& x) {
        pr("{",x.f,", ",x.s,"}");
    }
    tcT> void prContain(const T& x) {
        pr("{");
        bool fst = 1; trav(a,x) pr(!fst?", ":"",a), fst = 0;
        pr("}");
    }
    tcT, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); }
    tcT> void pr(const vector<T>& x) { prContain(x); }
    tcT> void pr(const set<T>& x) { prContain(x); }
    template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); }
 
    void ps() { pr("\n"); } // print w/ spaces
    template<class Arg> void ps(const Arg& first) { pr(first,"\n"); }
    template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) {
        pr(first," "); ps(rest...);
    }
}
 
using namespace output;
 
template <int MOD_> struct modnum {
	static constexpr int MOD = MOD_;
	static_assert(MOD_ > 0, "MOD must be positive");
 
private:
	using ll = long long;
 
	int v;
 
	static int minv(int a, int m) {
		a %= m;
		assert(a);
		return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
	}
 
public:
 
	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int() const { return v; }
	friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
	friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
 
	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
 
	modnum inv() const {
		modnum res;
		res.v = minv(v, MOD);
		return res;
	}
	friend modnum inv(const modnum& m) { return m.inv(); }
	modnum neg() const {
		modnum res;
		res.v = v ? MOD-v : 0;
		return res;
	}
	friend modnum neg(const modnum& m) { return m.neg(); }
 
	modnum operator- () const {
		return neg();
	}
	modnum operator+ () const {
		return modnum(*this);
	}
 
	modnum& operator ++ () {
		v ++;
		if (v == MOD) v = 0;
		return *this;
	}
	modnum& operator -- () {
		if (v == 0) v = MOD;
		v --;
		return *this;
	}
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= o.inv();
	}
 
	friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
	friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};
 
void setF(string fileName = "") {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if((int)fileName.size()) {
		freopen((fileName+".in").c_str(), "r", stdin);
		freopen((fileName+".out").c_str(), "w", stdout);
	}
}
 
vi SIEVE(int N){ // sieve in O(N)
	vi pr;
	vb b(N);
	vi g(N);
	F0R(i,2,N){
		if(!b[i]){
			pr.pb(i);
			for (int j = i + i; j < N; j += i) b[j] = true;
			}
		}
	return pr;
	}
 
struct DSU {
	vector<int> e;
	DSU(int N) { e = vector<int>(N, -1); }
 
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
 
	bool same_set(int a, int b) { return get(a) == get(b); }
 
	int size(int x) { return -e[get(x)]; }
 
	bool unite(int x, int y) {  // union by size
		x = get(x), y = get(y);
		if (x == y) return false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y]; e[y] = x;
		return true;
	}
};

template<class T> using ordset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct edge{
	int a;
	int b;
	int w;
	};
 
ll POW(ll x, ll y,ll mod = INF){
    ll res = 1LL;
    x %= mod;
    while(y){
        if (y & 1LL)
            res *= x;
        res %= mod;
        x = (x*x) % mod;
        y >>= 1LL;
    }
    return res;
}
 
ll gauss(ll n) { return n * (n + 1ll) / 2; }
 
ll fact(ll x) { if(x) return x * fact(x - 1ll); return 1; }
 
vl fc;
void F(int N,ll MOD){
	fc.rsz(N + 1);
	fc[0] = 1;
	FORn(i,N) fc[i] = fc[i - 1] * i * 1ll % MOD;
	}
	
vl inv;
void I(int N,ll MOD){
	inv.rsz(N + 1);
	inv[N] = POW(fc[N],MOD - 2,MOD);
	for (int i = N; i ;--i) inv[i - 1] = inv[i] * 1ll * i % MOD;
	}
 
ll Cr(ll N,ll K,ll mod){
	if(K < 0) return 0;
	if(K > N) return 0;
	return fc[N] * 1ll * inv[K] % mod * inv[N - K] % mod;
	}
ll iv(int k,ll MOD){
  return POW(k,MOD-2,MOD);  
}
/*
 scanf("%lld", &testInteger);
 printf("%lld", testInteger);
 
 ____ ____ ____ ____ ____  ____
||f |||l |||o |||p |||p ||||y ||
||__|||__|||__|||__|||__||||__||
|/__\|/__\|/__\|/__\|/__\||/__\|
 
**/
int N;
vi A;
struct Node{
		int mxp,mxs,val,ans;
		Node operator+(Node b){
			Node ret;
			ret.mxp = max(mxp,val + b.mxp);
			ret.mxs = max(b.mxs,b.val + mxs);
			ret.val = val + b.val;
			ret.ans = max({val + b.ans,ans + b.val,mxp + b.mxs});
			return ret;
			}
		};
int give(char a){
	return (a == 'T' ? 1 : -1);
	}
template <class T> class SEG {
	 private:
		int n;
	public:
		Node c[2000001];
		void init(int N) { n = 4 * N; memset(c,0,sizeof c); }
		void build(int l,int r,int x){
			if(l == r){
				if(A[l] == 1) c[x] = {1,1,1,1};
				else c[x] = {0,0,-1,0};
				return;
				}
			int mid = (l + r) / 2;
			build(l,mid,2 * x);
			build(mid + 1,r,2 * x + 1);
			c[x] = c[2 * x] + c[2 * x + 1];
			}
		void build(){
			build(1,N,1);
			}
		Node query(int a,int b,int l,int r,int x){
			if(a <= l && r <= b) return c[x];
			if(a > r || b < l) return {0,0,0,0};
			int mid = (l + r) / 2;
			return query(a,b,l,mid,2 * x) + query(a,b,mid + 1,r,2 * x + 1); 
			}
		Node query(int l,int r){
			return query(l,r,1,N,1);
			}
	};
template <class T> class BIT { // 1 indexed
  private:
	int n;
	vector<T> c;
	vector<T> a;

  public:
	BIT(int N) : n(N),c(N + 1),a(N + 1){};
	
	T sum(int i){
		if(i <= 0 || i > n) return 0;
		return c[i] + sum(i - (i & -i));
		}
	
	void add(int i,int v){
		if(i > n || i <= 0) return;
		for (int k = i; k <= n; k += (k & -k)) c[k] += v;
		}
	
	};
void solve() {
	cin >> N;
	str S; cin >> S;
	A.rsz(N + 1);
	FORn(i,N) A[i] = give(S[i - 1]);
	int Q; cin >> Q;
	SEG<ll>C;
	C.init(N);
	C.build();
	while(Q--){
		int l,r; cin >> l >> r;
		cout << C.query(l,r).ans << '\n';
		}
	
}
main()
{   setIO();
	solve();
}
// look out for out of bounds arrays
// And more importantly, is y a vowel? Damian:1
// <3 :L ._. <_<
// You have no idea how high I can fly

Compilation message

election.cpp:430:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  430 | main()
      | ^~~~
election.cpp: In function 'void setF(std::string)':
election.cpp:255:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  255 |   freopen((fileName+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:256:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  256 |   freopen((fileName+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 31572 KB Output is correct
2 Correct 17 ms 31644 KB Output is correct
3 Correct 16 ms 31608 KB Output is correct
4 Correct 17 ms 31572 KB Output is correct
5 Correct 17 ms 31520 KB Output is correct

Subtask #2
54.0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 31572 KB Output is correct
2 Correct 17 ms 31644 KB Output is correct
3 Correct 16 ms 31608 KB Output is correct
4 Correct 17 ms 31572 KB Output is correct
5 Correct 17 ms 31520 KB Output is correct
6 Correct 66 ms 33004 KB Output is correct
7 Correct 56 ms 33224 KB Output is correct
8 Correct 58 ms 33304 KB Output is correct
9 Correct 57 ms 33168 KB Output is correct
10 Correct 63 ms 33172 KB Output is correct
11 Correct 68 ms 33304 KB Output is correct
12 Correct 60 ms 33308 KB Output is correct
13 Correct 57 ms 33280 KB Output is correct
14 Correct 62 ms 33228 KB Output is correct
15 Correct 59 ms 33228 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 31572 KB Output is correct
2 Correct 17 ms 31644 KB Output is correct
3 Correct 16 ms 31608 KB Output is correct
4 Correct 17 ms 31572 KB Output is correct
5 Correct 17 ms 31520 KB Output is correct
6 Correct 66 ms 33004 KB Output is correct
7 Correct 56 ms 33224 KB Output is correct
8 Correct 58 ms 33304 KB Output is correct
9 Correct 57 ms 33168 KB Output is correct
10 Correct 63 ms 33172 KB Output is correct
11 Correct 68 ms 33304 KB Output is correct
12 Correct 60 ms 33308 KB Output is correct
13 Correct 57 ms 33280 KB Output is correct
14 Correct 62 ms 33228 KB Output is correct
15 Correct 59 ms 33228 KB Output is correct
16 Correct 449 ms 43812 KB Output is correct
17 Correct 374 ms 43300 KB Output is correct
18 Correct 481 ms 43660 KB Output is correct
19 Correct 350 ms 43104 KB Output is correct
20 Correct 478 ms 42928 KB Output is correct
21 Correct 443 ms 44736 KB Output is correct
22 Correct 471 ms 44584 KB Output is correct
23 Correct 469 ms 44832 KB Output is correct
24 Correct 469 ms 44480 KB Output is correct
25 Correct 440 ms 43900 KB Output is correct