### noob084's blog

By noob084, history, 3 years ago, ,

How can i make this approach more efficient to get AC. Can anyone help?

Suggestion is appreciated. :)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#define pb push_back
#define ll long long int
#define ull unsigned long long int
#define gcd(a,b)    __gcd(a,b)
#define sz sizeof
#define INF 1000000000000000000LL
#define ms memset
#define MAX

using namespace std;

int a[100010],tree[4*100010],lazy[4*100010];
void build(int node,int s,int d){
if(s==d){
//cout<<"node: "<<node<<" val: "<<a[s]<<endl;
tree[node] = a[s];
return;
}
int Left = node*2;
int Right = node*2 + 1;
int mid = (s+d)/2;
build(Left,s,mid);
build(Right,mid+1,d);

//update tree
tree[node] = tree[Left] + tree[Right];
}
void update(int node,int s,int d,int i,int j){
if(lazy[node]!=0){
if(lazy[node]%2==0){
// do nothing
}else{
tree[node] = (d-s+1) - tree[node];
}

if(s!=d){
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node]=0;
}

//no overlap
if(s>j || d<i) return;
//total overlap
if(s>=i && d<=j){
tree[node] = (d-s+1) - tree[node];

if(s!=d){
lazy[node*2]++;
lazy[node*2+1]++;
}
return ;
}
//partial overlap
int Left = node*2;
int Right = node*2 + 1;
int mid = (s+d)/2;
update(Left,s,mid,i,j);
update(Right,mid+1,d,i,j);

//update tree
tree[node] = tree[Left] + tree[Right];
}
int query(int node,int s,int d,int i,int j){
if(lazy[node]!=0){
if(lazy[node]%2==0){
// do nothing
}else{
tree[node] = (d-s+1) - tree[node];
}

if(s!=d){
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node]=0;
}

//no overlap
if(s>j || d<i){
return 0;
}
//total overlap
if(s>=i && d<=j){
return tree[node];
}
//partial overlap
int Left = node*2;
int Right = node*2 + 1;
int mid = (s+d)/2;
int p1=0,p2=0;
p1 = query(Left,s,mid,i,j);
p2 = query(Right,mid+1,d,i,j);
return p1+p2;
}

int main()
{
//freopen("a.in","r",stdin);
//freopen("out.txt","w",stdout);
//std::ios_base::sync_with_stdio(false);
int n,t,i,j,cases=1,q,u,v;
scanf("%d",&t);
getchar();
while(t--){
ms(a,0,sz(a));
ms(tree,0,sz(tree));
ms(lazy,0,sz(lazy));
char s[100010];
scanf("%s",&s);
for(i=0;i<strlen(s);i++){
a[i+1] = s[i]-'0';
}
n = strlen(s);
build(1,1,n);
printf("Case %d:\n",cases);cases++;
scanf("%d",&q);
getchar();
char ch;
while(q--){
scanf("%c",&ch);
if(ch=='I'){
scanf("%d %d",&u,&v);
update(1,1,n,u,v);
}else{
scanf("%d",&u);
int bit = query(1,1,n,u,u);
printf("%d\n",bit);
}
getchar();
}
}

return 0;
}



• 0

By noob084, history, 4 years ago, ,

Here is the link of the problem : http://lightoj.com/volume_showproblem.php?problem=1135 link of code: https://ideone.com/h3Zu5C

Getting Runtime Error(RTE). Also in this problem: https://www.codechef.com/problems/MULTQ3

Can anyone help? Why getting RTE? Thanks in advance.