Getting TLE in 1080 — Binary Simulation

Revision en1, by noob084, 2017-01-21 12:55:53

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;
}



#### History

Revisions

Rev. Lang. By When Δ Comment
en1 noob084 2017-01-21 12:55:53 3658 Initial revision (published)