| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 952614 |
2024-03-24T11:03:58 Z |
Danet |
Election (BOI18_election) |
C++14 |
|
100 ms |
219508 KB |
#include <bits/stdc++.h>
using namespace std;
#define Tof_Io ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
#define kill(x) cout << x << endl, exit(0)
#define all(x) x.begin(),x.end()
#define int long long int
#define pb push_back
#define endl '\n'
const int N = 4e6 + 23;
const int mod = 998244353; //998244353
const int inf = 1e9 + 2;
vector<int> adj[N];
string str;
vector<int> vc;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int p[4] = {'^', '<', 'v', '>'};
/*************************************BUILD*************************************/
/***********************************FcolNCTION***********************************/
int n , q;
string s;
struct node{
pair<int,int> ty;
int sum;
int ans;
};
node seg[N];
void update(int v, int tl, int tr, int pos, int val)
{
if (tl == tr)
{
seg[v].ty.first = max(seg[v].ty.first, val);
seg[v].ty.second = max(seg[v].ty.second, val);
seg[v].sum = seg[v].sum + val;
seg[v].ans = 1;
seg[v].ans = ((val == -1) ? 0 : 1);
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm) update(2 * v, tl, tm, pos, val);
else update(2 * v + 1, tm + 1, tr, pos, val);
//
seg[v].ty.first = max (seg[2*v].ty.first , seg[2*v+1].ty.first);
seg[v].ty.second = max (seg[2*v].ty.second , seg[2*v+1].ty.second);
seg[v].sum = seg[2*v].sum + seg[2*v+1].sum;
seg[v].ans = max(seg[2*v].ans + seg[2*v+1].sum , seg[2*v].sum + seg[2*v+1].ans);
seg[v].ans = max(seg[v].ans , seg[2*v].ty.first + seg[2*v+1].ty.second);
}
node query(int v, int tl, int tr, int l, int r)
{
if (tl > r or tr < l) return {make_pair(0ll,0ll), 0 , 0};
if (tl >= l and tr <= r) return seg[v];
int tm = (tl + tr) / 2;
node L = query(2*v, tl, tm, l, r);
node R = query(2*v+1, tm + 1, tr, l, r);
node ret;
ret.ty.first = max(L.ty.first , R.ty.first); ret.ty.second = max(L.ty.second , R.ty.second);
ret.sum = L.sum + R.sum;
ret.ans = max(L.ans + R.sum , L.sum + R.ans);
ret.ans = max(ret.ans , L.ty.first + R.ty.second);
return ret;
}
int32_t main()
{
cin >> n >> s >> q;
for(int i = 0; i < s.length(); i++)
{
if(s[i] == 'C')
{
update(1, 1, n, i + 1, -1);
}
else
{
update(1, 1, n, i + 1, 1);
}
}
while(q--)
{
int l, r;
cin >> l >> r;
cout << query(1, 1, n, l, r).ans;
cout << endl;
}
}
Compilation message
election.cpp: In function 'int32_t main()':
election.cpp:72:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i = 0; i < s.length(); i++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
219508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
219508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
219508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
