Submission #310451

#TimeUsernameProblemLanguageResultExecution timeMemory
310451arwaeystoamnegElection (BOI18_election)C++17
100 / 100
736 ms70536 KiB
/* ID: awesome35 LANG: C++14 TASK: milk4 */ #define _CRT_SECURE_NO_WARNINGS #include<bits/stdc++.h> #include<unordered_set> #include<unordered_map> #include<chrono> using namespace std; typedef pair<int, int> pii; typedef long long ll; typedef pair<ll, ll> pll; typedef long double ld; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pair<int, int>> vpi; typedef vector<pair<ll, ll>> vpll; #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 trav(a,x) for (auto& a: x) #define pb push_back #define mp make_pair #define rsz resize #define sz(x) int(x.size()) #define all(x) x.begin(),x.end() #define f first #define s second #define cont continue #define endl '\n' #define ednl '\n' #define test int testc;cin>>testc;while(testc--) #define pq priority_queue const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!! const ll linf = 4000000000000000000LL; const ll inf = 1000000007;//998244353 const ld pi = 3.1415926535; void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) { F0R(i, a.size()) { cout << i << endl; pv(a[i]); cout << endl; } }void pv(vector<vll>a) { F0R(i, a.size()) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; } void build_primes(vi& primes, int size) { vi visited; visited.rsz(size, 0); FOR(i, 2, size) { if (visited[i] == 0) { primes.pb(i); int a = i; while (a < size) { visited[a] = 1; a += i; } } } } vector<vector<ll>> matrix_mult(vector<vector<ll>>& a, vector<vector<ll>>& b) { int n = a.size(); vector<vector<ll>> answer; answer.resize(n); for (int i = 0; i < n; i++) answer[i].resize(n, 0); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) // calculate answer[i][j] { for (int k = 0; k < n; k++) answer[i][j] = (answer[i][j] + a[i][k] * b[k][j]) % inf; } } return answer; } int modInverse(int a, int m) { int m0 = m; int y = 0, x = 1; if (m == 1) return 0; while (a > 1) { // q is quotient int q = a / m; int t = m; // m is remainder now, process same as // Euclid's algo m = a % m, a = t; t = y; // Update y and x y = x - q * y; x = t; } // Make x positive if (x < 0) x += m0; return x; } ll power(ll x, ll y) { ll k = 1 << 30; ll z = 1; while (k != 0) { z *= z; z %= inf; if (y >= k) { z *= x; z %= inf; y -= k; } k >>= 1; } return z; } struct point { ld x, y; }; struct pt { ll x, y; }; // remember that you need to take abs long double area(point x, point y, point z) { return (x.y * y.x + y.y * z.x + z.y * x.x - x.x * y.y - y.x * z.y - z.x * x.y) / 2.0; } bool clockwise(point x, point y, point z) { return area(x, y, z) > 0; } // remember that you need to take abs long double area(pt x, pt y, pt z) { return (x.y * y.x + y.y * z.x + z.y * x.x - x.x * y.y - y.x * z.y - z.x * x.y) / 2.0; } bool clockwise(pt x, pt y, pt z) { return area(x, y, z) > 0; } int gcd(int a, int b) { if (a > b)swap(a, b); if (a == 0)return b; return gcd(a, b % a); } int popcount(int a) { int count = 0; while (a != 0) { count += (a % 2); a >>= 1; } return count; } ll choose(ll n, ll r) { ll p = 1, k = 1; if (n - r < r) r = n - r; if (r != 0) { while (r) { p *= n; k *= r; long long m = gcd(p, k); p /= m; k /= m; n--; r--; } } else p = 1; return p; } vll prefix_hash(string& a, vll& powers) { int n = sz(a); vll prefix(n + 1); F0R(i, n)prefix[i + 1] = (prefix[i] + powers[i] * (a[i] - 'a' + 1)) % inf; return prefix; } struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; struct custom_hash_fast { size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); x ^= FIXED_RANDOM; return x ^ (x >> 16); } }; class segment_tree { struct item { ll sum, prefix, suffix, ans; }; item single(ll i) { if (i == 1) return { i,1,1 }; return { i,0,0 }; } item merge(item x, item y) { item ans = { 0,0,0,0 }; ans.sum = x.sum + y.sum; ans.prefix = max(x.prefix, y.prefix + x.sum); ans.suffix = max(y.suffix, x.suffix + y.sum); ans.ans = max({ x.ans + y.sum,x.sum + y.ans,x.prefix + y.suffix }); return ans; } vector<item> tree; vector<item>A; int height; item neutral = { 0,0,0,0 }; public:void build(vll& B) { int n = B.size(); height = log2(n - 1) + 1; A.rsz(n); tree.rsz((1 << height + 1) - 1); F0R(i, n)A[i] = single(B[i]); A.rsz(1 << height, neutral); build(A, 0, 0, (1 << height) - 1); } void build(vector<item>& A, int v, int tl, int tr) { if (tl == tr) tree[v] = A[tl]; else { int mid = (tl + tr) / 2; build(A, 2 * v + 1, tl, mid); build(A, 2 * v + 2, mid + 1, tr); tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]); } } public:ll query(int l, int r) { item ans = query(0, 0, (1 << height) - 1, l, r); return ans.ans; } item query(int v, int tl, int tr, int l, int r) { if (r<tl || l>tr)return neutral; if (l <= tl && r >= tr) { return tree[v]; } int mid = (tl + tr) / 2; return merge(query(2 * v + 1, tl, mid, l, r), query(2 * v + 2, mid + 1, tr, l, r)); } //assign public:void update(int pos, int val) { update(0, 0, (1 << height) - 1, pos, single(val)); } void update(int v, int tl, int tr, int pos, item val) { if (tl == tr) { tree[v] = val; } else { int mid = (tl + tr) / 2; if (pos <= mid) update(2 * v + 1, tl, mid, pos, val); else update(2 * v + 2, mid + 1, tr, pos, val); tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]); } } }; void setIO(string s) { ios_base::sync_with_stdio(0); cin.tie(0); //freopen((s + ".in").c_str(), "r", stdin); //freopen((s + ".out").c_str(), "w", stdout); } int main() { setIO("test1"); int n; string a; cin >> n >> a; vll t(n); F0R(i, n)t[i] = (a[i] == 'C' ? -1 : 1); segment_tree m; m.build(t); test { int l,r; cin >> l >> r; cout << m.query(l - 1, r - 1) << endl; } }

Compilation message (stderr)

election.cpp: In function 'void pv(std::vector<std::vector<int> >)':
election.cpp:22:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
election.cpp:23:18: note: in expansion of macro 'FOR'
   23 | #define F0R(i,a) FOR(i,0,a)
      |                  ^~~
election.cpp:46:2: note: in expansion of macro 'F0R'
   46 |  F0R(i, a.size()) { cout << i << endl; pv(a[i]); cout << endl; }
      |  ^~~
election.cpp: In function 'void pv(std::vector<std::vector<long long int> >)':
election.cpp:22:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
election.cpp:23:18: note: in expansion of macro 'FOR'
   23 | #define F0R(i,a) FOR(i,0,a)
      |                  ^~~
election.cpp:47:26: note: in expansion of macro 'F0R'
   47 | }void pv(vector<vll>a) { F0R(i, a.size()) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
      |                          ^~~
election.cpp: In member function 'void segment_tree::build(vll&)':
election.cpp:244:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  244 |  tree.rsz((1 << height + 1) - 1);
      |                 ~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...