/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;
struct{
int first;
int second;
int third;
int fourth;
int fifth;
}tree[2000001];
vector<int> merge(int x1,int y1,int z1, int x2, int y2,int z2, int x3, int y3,int z3, int x4, int y4, int z4){
int profit = z1 + x1;
int prvo = x1 + max(0,x3 - profit);
int z = max(0,y4 - y3 - max(0, x3 - profit));
profit = y3 + z + max(0,x3 - profit) + z3;
int drugo = y3 + z + max(0, y1 - profit);
profit = y4 + z4;
int cetvrto = y4 + max(0, y2 - profit);
z = max (0, x1 - x2 - max(0, y2 - profit));
profit = z + x2 + max(0, y2 - profit) + z2;
int trece = z + x2+ max(0, x4 - profit);
vector<int>ans;
ans.push_back(prvo);
ans.push_back(drugo);
ans.push_back(trece);
ans.push_back(cetvrto);
return ans;
}
void update (int node, int start, int end, int idx, int val1, int val2, int val3, int val4,int val){
if(start == end){
tree[node].first = val1;
tree[node].second = val2;
tree[node].third = val3;
tree[node].fourth = val4;
tree[node].fifth += val;
}else{
int mid = (start + end)/2;
if(start <= idx and idx <= mid){
update(2*node, start, mid, idx, val1, val2, val3, val4,val);
}else{
update(2*node + 1, mid + 1, end , idx, val1, val2, val3, val4,val);
}
int node1 = 2*node;
int node2 = 2*node + 1;
int x1 = tree[node1].first;
int y1 = tree[node1].second;
int z1 = tree[node1].fifth;
int x2 = tree[node1].third;
int y2 = tree[node1].fourth;
int z2 = tree[node1].fifth;
int x3 = tree[node2].first;
int y3 = tree[node2].second;
int z3 = tree[node2].fifth;
int x4 = tree[node2].third;
int y4 = tree[node2].fourth;
int z4 = tree[node2].fifth;
vector<int> v = merge(x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4);
tree[node].first = v[0];
tree[node].second = v[1];
tree[node].third = v[2];
tree[node].fourth = v[3];
tree[node].fifth = tree[2*node].fifth + tree[2*node+1].fifth;
}
}
vector<int>tren;
int sum = 0;
void query(int node, int start, int end, int l, int r){
if(r < start or end < l){
return;
}
if(l<= start and end <= r){
if(tren.empty()){
tren.push_back(tree[node].first);
tren.push_back(tree[node].second);
tren.push_back(tree[node].third);
tren.push_back(tree[node].fourth);
}else{
tren = merge(tren[0], tren[1], sum, tren[2], tren[3],sum, tree[node].first, tree[node].second,tree[node].fifth, tree[node].third, tree[node].fourth,tree[node].fifth);
}
sum = sum +tree[node].fifth;
return;
}
int mid = (start + end)/2;
query(2*node, start, mid, l, r);
query(2*node +1 , mid +1 , end , l, r);
}
int main()
{
int n;
cin >> n;
string s;
cin >> s;
for(int i = 0; i < n; i++){
if(s[i] == 'C'){
update(1, 0, n-1, i, 0, 0, 0, 0,1);
}else{
update(1, 0, n - 1, i, 1, 0, 0, 1,-1);
}
}
int q;
cin >> q;
vector<int>ans;
//cout<<query(1,0,n)
while(q--){
int a, b;
cin >> a >> b;
a --;
b --;
tren.clear();
sum = 0;
query(1, 0, n - 1, a, b);
// cout << tren[0]<<" "<<tren[1]<<" "<<tren[2]<<" "<<tren[3]<<endl;
ans.push_back(tren[0] + tren[1]);
}
for (int i = 0; i < ans.size(); i++){
cout<<ans[i]<<endl;
}
return 0;
}
Compilation message
election.cpp: In function 'int main()':
election.cpp:129:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for (int i = 0; i < ans.size(); i++){
| ~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
348 KB |
Output is correct |
| 2 |
Correct |
6 ms |
512 KB |
Output is correct |
| 3 |
Correct |
6 ms |
348 KB |
Output is correct |
| 4 |
Correct |
6 ms |
348 KB |
Output is correct |
| 5 |
Correct |
6 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
348 KB |
Output is correct |
| 2 |
Correct |
6 ms |
512 KB |
Output is correct |
| 3 |
Correct |
6 ms |
348 KB |
Output is correct |
| 4 |
Correct |
6 ms |
348 KB |
Output is correct |
| 5 |
Correct |
6 ms |
348 KB |
Output is correct |
| 6 |
Correct |
264 ms |
8256 KB |
Output is correct |
| 7 |
Correct |
278 ms |
8272 KB |
Output is correct |
| 8 |
Correct |
265 ms |
8384 KB |
Output is correct |
| 9 |
Correct |
241 ms |
8280 KB |
Output is correct |
| 10 |
Correct |
247 ms |
8132 KB |
Output is correct |
| 11 |
Correct |
261 ms |
8212 KB |
Output is correct |
| 12 |
Correct |
256 ms |
8212 KB |
Output is correct |
| 13 |
Correct |
265 ms |
8560 KB |
Output is correct |
| 14 |
Correct |
261 ms |
8248 KB |
Output is correct |
| 15 |
Correct |
249 ms |
8144 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
348 KB |
Output is correct |
| 2 |
Correct |
6 ms |
512 KB |
Output is correct |
| 3 |
Correct |
6 ms |
348 KB |
Output is correct |
| 4 |
Correct |
6 ms |
348 KB |
Output is correct |
| 5 |
Correct |
6 ms |
348 KB |
Output is correct |
| 6 |
Correct |
264 ms |
8256 KB |
Output is correct |
| 7 |
Correct |
278 ms |
8272 KB |
Output is correct |
| 8 |
Correct |
265 ms |
8384 KB |
Output is correct |
| 9 |
Correct |
241 ms |
8280 KB |
Output is correct |
| 10 |
Correct |
247 ms |
8132 KB |
Output is correct |
| 11 |
Correct |
261 ms |
8212 KB |
Output is correct |
| 12 |
Correct |
256 ms |
8212 KB |
Output is correct |
| 13 |
Correct |
265 ms |
8560 KB |
Output is correct |
| 14 |
Correct |
261 ms |
8248 KB |
Output is correct |
| 15 |
Correct |
249 ms |
8144 KB |
Output is correct |
| 16 |
Correct |
2206 ms |
33740 KB |
Output is correct |
| 17 |
Correct |
2296 ms |
33208 KB |
Output is correct |
| 18 |
Correct |
2201 ms |
33756 KB |
Output is correct |
| 19 |
Correct |
1898 ms |
33552 KB |
Output is correct |
| 20 |
Correct |
2104 ms |
32860 KB |
Output is correct |
| 21 |
Correct |
2116 ms |
34524 KB |
Output is correct |
| 22 |
Correct |
2138 ms |
34312 KB |
Output is correct |
| 23 |
Correct |
2145 ms |
34676 KB |
Output is correct |
| 24 |
Correct |
2120 ms |
34396 KB |
Output is correct |
| 25 |
Correct |
2096 ms |
34032 KB |
Output is correct |
