Блог пользователя noob084

Автор noob084, история, 8 лет назад, По-английски

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

Problem link: 1080-Binary Simulation
Code ideone link: code

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
  • Проголосовать: не нравится