| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1108071 |
2024-11-02T16:43:19 Z |
matu |
Election (BOI18_election) |
C++17 |
|
2 ms |
592 KB |
#include <bits/stdc++.h>
// #include <tr2/dynamic_bitset>
using namespace std;
// using namespace tr2;
#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const long double eps = 1e-9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randgen(int left, int right) {
return uniform_int_distribution<int>(left, right)(rng);
}
long long randgenll(long long left, long long right) {
return uniform_int_distribution<long long>(left, right)(rng);
}
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
struct Mint
{
int val;
Mint(int x = 0)
{
val = x % mod;
}
Mint(long long x)
{
val = x % mod;
}
Mint operator+(Mint oth)
{
return val + oth.val;
}
Mint operator*(Mint oth)
{
return 1LL * val * oth.val;
}
Mint operator-(Mint oth)
{
return val - oth.val + mod;
}
Mint fp(Mint a, long long n){
Mint p = 1;
while(n){
if(n & 1){
p = p * a;
}
a = a * a;
n /= 2;
}
return p;
}
Mint operator/(Mint oth){
Mint invers = fp(oth, mod - 2);
return 1LL * val * invers.val;
}
friend ostream& operator << (ostream& os, const Mint& lol){
os << lol.val;
return os;
}
};
struct AINT{
vector<ll> aint;
vector<ll> lazy;
AINT(int n){
aint.assign(n * 4 + 1,-1e9);
//lazy.assign(n * 4 + 1, -1);
}
void update(int v, int tl, int tr, int pos, int val){
if(tl == tr){
aint[v] = val;
return;
}
int tm = (tl + tr) / 2;
if(pos <= tm) update(v * 2, tl ,tm, pos, val);
else update(v * 2 + 1, tm + 1, tr, pos,val);
aint[v] = max(aint[v * 2], aint[v * 2 + 1]);
}
int query(int v, int tl, int tr, int l, int r){
int tm = (tl + tr) / 2;
if(l <= tl && r >= tr) return aint[v];
if(l > tr || r < tl) return -1e9;
return max(query(v * 2, tl, tm,l,r), query(v * 2 + 1, tm + 1, tr, l,r));
}
};
struct AIB{
vector<int> aib;
AIB(int n){
aib.assign(n + 1,0);
}
void update(int pos, int val){
for(; pos < aib.size(); pos += (pos & -pos)){
aib[pos] += val;
}
}
int query(int pos){
int pl = 0;
for(; pos > 0; pos -= (pos & -pos)) pl += aib[pos];
return pl;
}
};
int red = 0;
int ______________________________________________________________________________________________________________________________________________;
void solve(){
int n;
cin >> n;
string s;
cin >> s;
s = '.' + s;
vector<int> sp1(n + 1), sp2(n + 2);
AINT aint1(n + 1), aint2(n + 1);
for(int i = 1; i <= n; i++){
sp1[i] = sp1[i-1] + (s[i] == 'C' ? -1 : 1);
aint1.update(1, 1, n, i, sp1[i]);
}
for(int i = n; i >= 1; i--){
sp2[i] = sp2[i + 1] + (s[i] == 'C' ? -1 : 1);
aint2.update(1,1,n,i,sp2[i]);
}
int q;
cin >> q;
while(q--){
int l, r;
cin >> l >> r;
int pl = max(aint1.query(1,1,n, l,r) - sp1[l-1], aint2.query(1,1,n,l,r) - sp2[r+ 1]);
pl = max(pl,0);
cout << pl << '\n';
}
}
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
int t = 1;
if(red) cin >> t;
while(t--){
solve();
}
}
/*
4 1
0 0 1
j + 1 + p >= d
p >= d - j - 1
i + j >= d
j >= d - i;
*/
Compilation message
election.cpp: In member function 'void AIB::update(int, int)':
election.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(; pos < aib.size(); pos += (pos & -pos)){
| ~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
