Submission #705068

#TimeUsernameProblemLanguageResultExecution timeMemory
705068ZflopElection (BOI18_election)C++14
28 / 100
6 ms4744 KiB
#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; const int NMAX = (int)1e5; 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[NMAX]; 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 (stderr)

election.cpp:431:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  431 | 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);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...