/******************************************************************************
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 = z + max(0,x3 - profit);
int drugo = z + max(0, y1 - profit);
profit = y4 + z4;
int cetvrto = y4 + max(0, y2 - profit);
z = max (0, x2 - x1 - max(0, y2 - profit));
profit = z + max(0, y2 - profit);
int trece = z + 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;
vector<int>ro = merge(1,0,-1,0,1,-1,1,0,-1,0,1,-1);
for(int i = 0;i < ro.size();i++){
cout<<ro[i]<<endl;
}
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:116:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int i = 0;i < ro.size();i++){
| ~~^~~~~~~~~~~
election.cpp:131:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int i = 0; i < ans.size(); i++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
