| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 489203 |
2021-11-21T14:47:02 Z |
mat_v |
Election (BOI18_election) |
C++14 |
|
8 ms |
12108 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int n;
string x;
int niz[500005];
int q;
vector<pii> kveri[500005];
int tr = 0;
int sl[500005];
int lejzi[4 * 5000000 + 1];
int seg[4 * 5000000 + 1];
int bit[500005];
void apd(int x, int dlt){
while(x <= n){
bit[x] += dlt;
x += (x&-x);
}
}
int kv(int x){
int ans = 0;
while(x){
ans += bit[x];
x -= (x&-x);
}
return ans;
}
void propagate(int node, int l, int r){
if(lejzi[node] == 0)return;
seg[node] += lejzi[node];
if(l < r){
lejzi[node * 2] += lejzi[node];
lejzi[node * 2 + 1] += lejzi[node];
}
lejzi[node] = 0;
}
void update(int node, int l, int r, int levo, int desno, int val){
propagate(node, l, r);
if(levo > r || l > desno)return;
if(l >= levo && r <= desno){
seg[node] += val;
propagate(node, l, r);
return;
}
int mid = (l + r) / 2;
update(node * 2, l, mid, levo, desno, val);
update(node * 2 + 1, mid + 1, r, levo, desno, val);
seg[node] = min(seg[node * 2], seg[node * 2 + 1]);
}
int query(int node, int l, int r, int levo, int desno){
if(levo == 0)return 0;
propagate(node, l, r);
if(levo > r || l > desno)return 1e9;
if(l >= levo && r <= desno)return seg[node];
int mid = (l + r) / 2;
return min(query(node * 2, l, mid, levo, desno), query(node * 2 + 1 , mid + 1, r, levo, desno));
}
int ans[500005];
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> x;
ff(i,1,n){
if(x[i - 1] == 'C')niz[i] = 1;
else niz[i] = -1;
}
cin >> q;
ff(i,1,q){
int l,r;
cin >> l >> r;
kveri[r].pb({l,i});
}
ff(i,1,n){
if(niz[i] == -1){
sl[i] = tr;
tr = i;
apd(i,1);
}
else{
update(1,1,n,i,n,1);
if(tr){
update(1,1,n,tr,n,-1);
apd(tr,-1);
tr = sl[tr];
}
}
for(auto c:kveri[i]){
ans[c.yy] = -min(0,query(1,1,n,c.xx,i) - query(1,1,n,c.xx-1,c.xx-1)) + kv(i) - kv(c.xx - 1);
}
}
ff(i,1,q)cout << ans[i] << "\n";
return 0;
}
/*
11
CCCTTTTTTCC
1
1 11
*/
Compilation message
election.cpp: In function 'int main()':
election.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
election.cpp:93:5: note: in expansion of macro 'ff'
93 | ff(i,1,n){
| ^~
election.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
election.cpp:98:5: note: in expansion of macro 'ff'
98 | ff(i,1,q){
| ^~
election.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
election.cpp:103:5: note: in expansion of macro 'ff'
103 | ff(i,1,n){
| ^~
election.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
election.cpp:121:5: note: in expansion of macro 'ff'
121 | ff(i,1,q)cout << ans[i] << "\n";
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
12108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
12108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
12108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
