Light OJ: 1424 – New Land

0

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1424

Solution Idea: I think this problem can be solved with a 2D Segment Tree. But here I use the histogram technique to solve this problem. You can try Spoj – HISTOGRA – Largest Rectangle in a Histogram and Light OJ – 1083 – Histogram . Both are same problem on different website. This problems can be using a niche technique called histogram which can be implemented using a stack. the algorithm determine the index of the bar before the current bar which is smaller than the current bar also determine the index of the bar after the current bar which is smaller than the current bar. Here the function func is the answer of the above two problem.

In this problem for each row we consider a histogram from current row and the rows which are above the current row with continuous 0. Then determine the maximum answer.


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 2002

char grid[mx][mx];

int dp[mx][mx];

int func(int ara[], int n)
{
    int left[mx];

    stack<int>st;

    for(int i=0; i<n; i++)
    {
        while(!st.empty() && ara[st.top()]>=ara[i]) st.pop();
        left[i]=(st.empty()?-1:st.top());
        st.push(i);
    }

    while(!st.empty()) st.pop();

    int ret=0;
    int right;
    for(int i=n-1; i>=0; i--)
    {
        while(!st.empty() && ara[st.top()]>=ara[i]) st.pop();
        right=(st.empty()?n:st.top());
        ret=max((right-left[i]-1)*ara[i],ret);
        st.push(i);
    }
    return ret;
}

int main()
{

//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int t;
    sf(t);
    TEST_CASE(t)
    {
        int n,m;
        sff(n,m);
        getchar();
        for(int i=0; i<n; i++)
            sc("%s",grid[i]);

        for(int j=0; j<m; j++)
        {
            dp[0][j]=(grid[0][j]=='0')?1:0;
        }

        int ans=func(dp[0],m);

        for(int i=1; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                dp[i][j]=dp[i-1][j]+((grid[i][j]=='0')?1:-dp[i-1][j]);
            }
            ans=max(ans,func(dp[i],m));
        }
        PRINT_CASE;
        pf("%d\n",ans);

    }


    return 0;
}

Advertisements

ACM-ICPC Live Archive : 4108 – SKYLINE

0

Link: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2109

Solution Link: https://github.com/tanmoy13/ACM-ICPC-Live-Archive/blob/master/4108%20-%20SKYLINE.cpp


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 100005

struct data
{
    ll maxi, mini, prop;

};

struct inp
{
    int l, r, v;
    inp(int a, int b, int c)
    {
        l=a,r=b,v=c;
    }
};

data tree[mx*4];

int ls,rs,h;

void push_down(int n)
{
    int val=tree[n].prop;
    if(tree[n].prop!=0)
    {
        tree[n*2].prop=val;
        tree[n*2+1].prop=val;
        tree[n*2].maxi=val;
        tree[n*2+1].maxi=val;
        tree[n*2].mini=val;
        tree[n*2+1].mini=val;
        tree[n].prop=0;
    }
}

void push_up(int n)
{
    tree[n].maxi=max(tree[n*2].maxi,tree[n*2+1].maxi);
    tree[n].mini=min(tree[n*2].mini,tree[n*2+1].mini);
}

int anss=0;

void update(int n, int b, int e, int i, int j)
{
    if(b>j || e<i) return;
    if(b>=i && e<=j)
    {
        if(tree[n].maxi<h)
        {
            tree[n].maxi=h;
            tree[n].prop=h;
            tree[n].mini=h;
            return;
        }
        else if(tree[n].mini>h)
        {
            anss+=(e-b+1);
            return;
        }
    }
    if(b==e) return;
    push_down(n);
    int l=n*2;
    int r=l+1;
    int mid=(b+e)/2;
    update(l,b,mid,i,j);
    update(r,mid+1,e,i,j);
    push_up(n);
}

int main()
{

    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int t;
    int n;
    sf(t);
    {
        TEST_CASE(t)
        {
            sf(n);
            ll ans=0;

            ms(tree,0);

            vector<inp>vv;
            int rss=0;
            loop(i,n)
            {

                sfff(ls,rs,h);
                rss=max(rss,rs);
                vv.pb(inp(ls,rs,h));
            }

            for(int i=0; i<n; i++)
            {
                ls=vv[i].l;
                rs=vv[i].r;
                h=vv[i].v;
                anss=0;
                update(1,1,rss+3,ls,rs-1);
                ans+=(rs-ls-anss);

            }
            pf("%lld\n",ans);
        }
    }

    sf(t);

    return 0;
}


Light OJ: 1207 – Posters for Election

0

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1207


/*
     If opportunity doesn't knock, build a door.
 
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |S|.|S|.|R|.|A|.|S|.|A|.|M|.|K|
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 
    Success is how high you bounce when you hit bottom.
*/
 
 
#include <bits/stdc++.h>
 
#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))
 
using namespace std;
 
 
/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/
 
/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/
 
struct data
{
    int sum, prop;
};
 
data tree[3*200005];
 
void push_down(int n, int b, int e)
{
    if(tree[n].prop!=-1)
    {
        int mid=(b+e)/2;
        tree[n*2].sum=(mid-b+1)*tree[n].prop;
        tree[n*2+1].sum=(e-mid)*tree[n].prop;
        tree[2*n].prop=tree[n].prop;
        tree[2*n+1].prop=tree[n].prop;
        tree[n].prop=-1;
    }
}
 
 
void push_up(int n)
{
    tree[n].sum=tree[n*2].sum+tree[n*2+1].sum;
}
 
void update(int n, int b, int e, int i, int j, int x)
{
    if(i>e || j<b) return;
    if(b>=i && e<=j)
    {
        tree[n].sum=x;
        tree[n].prop=x;
        return;
    }
 
    push_down(n,b,e);
 
    int l=n*2;
    int r=l+1;
    int mid=(b+e)/2;
 
    update(l,b,mid,i,j,x);
    update(r,mid+1,e,i,j,x);
 
    push_up(n);
 
}
 
bool query(int n, int b, int e, int i, int j)
{
    if(i>e || j<b) return 0;
    if(b>=i && e<=j) return tree[n].sum;
    push_down(n, b, e);
    int l=n*2;
    int r=l+1;
    int mid=(b+e)/2;
 
    int p=query(l,b,mid,i,j);
    int q=query(r,mid+1,e,i,j);
    push_up(n);
    return p|q;
}
 
int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
 
    int t;
    sf(t);
    TEST_CASE(t)
    {
        vector<pii>v;
        int n;
        sf(n);
 
        loop(i,n)
        {
            int a,b;
            sff(a,b);
            v.pb(MP(a,b));
        }
        reverse(all(v));
 
        int ans=0;
 
        update(1,1,200000,1,200000,1);
 
        loop(i,n)
        {
            if(query(1,1,200000,v[i].ff,v[i].ss))
            {
                ans++;
                update(1,1,200000,v[i].ff,v[i].ss,0);
            }
        }
        PRINT_CASE;
        printf("%d\n",ans);
    }
 
 
    return 0;
}

Light OJ: 1097 – Lucky Number

0

Problem Link: http://www.lightoj.com/volume_showproblem.php?problem=1097



/*
     If opportunity doesn't knock, build a door.

            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |S|.|S|.|R|.|A|.|S|.|A|.|M|.|K|
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    Success is how high you bounce when you hit bottom.
*/


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int mm=1429431;

int tree[1429450*4];

void init(int n,int b, int e)
{
    if(b==e)
    {
        if(b%2==1) tree[n]=1;
        else tree[n]=0;
        return;
    }
    int mid=(b+e)/2;
    int l=n*2;
    int r=l+1;
    init(l,b,mid);
    init(r,mid+1,e);
    tree[n]=tree[l]+tree[r];
}

int query(int n, int b, int e, int x)
{
    if(x==1 && b==e) return b;
    int l=n*2;
    int r=l+1;
    int mid=(b+e)/2;
    if(x>tree[l]) return query(r,mid+1,e,x-tree[l]);
    else
        return query(l,b,mid,x);
}

void update(int n, int b, int e, int x)
{
    if(x==1 && b==e)
    {
        tree[n]=0;
        return;
    }
    int l=n*2;
    int r=l+1;
    int mid=(b+e)/2;
    if(x>tree[l]) update(r,mid+1,e,x-tree[l]);
    else
        update(l,b,mid,x);
    tree[n]=tree[l]+tree[r];
}

int main()
{

//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);

    init(1,1,mm);
    for(int i=2; i<=100000; i++)
    {
        int x=query(1,1,mm,i);
        int xx=x;
        while(x<tree[1])
        {
            update(1,1,mm,x);
            x+=xx;
            x-=1;
        }
    }

    int t;
    sf(t);
    TEST_CASE(t)
    {
        int a;
        sf(a);
        PRINT_CASE;
        pf("%d\n",query(1,1,mm,a));
    }
    return 0;
}

1089 – Points in Segments (II)

0

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1089


/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<=b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d:\n",z)
#define CASE_PRINT      cout<<"Case "<<z<<": ";
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int ara[200006];


int main()
{
//    freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int t;
    sf(t);
    TEST_CASE(t)
    {
        vector<int> v;
        vector<pii> segment;
        map<int,int>mp;
        map<int,bool> vis;
        int n,q,a,b,range=-1;
        sff(n,q);

        loop(i,n)
        {

            sff(a,b);
            if(a>b) swap(a,b);
            segment.pb(MP(a,b));
            if(!vis[a])
            {
                v.pb(a);
                vis[a]=1;
            }
            if(!vis[b])
            {
                v.pb(b);
                vis[b]=1;
            }
        }

        sort(all(v));

        int cnt=1;

        loop(i,SZ(v))
        {
            mp[v[i]]=cnt;
            cnt+=2;
        }

        loop(i,SZ(segment))
        {
            ara[mp[segment[i].ff]]++;
            ara[mp[segment[i].ss]+1]--;
        }

        REP(i,1,cnt) ara[i]+=ara[i-1];

//        loop(i,SZ(v)) cout<<v[i]<<" ";
//        cout<<endl;
//        D(mp[v[2]]);

        PRINT_CASE;
        while(q--)
        {
            sf(a);
            int x=lower_bound(all(v),a)-v.begin();
            if(x==SZ(v))
            {
                pf("0\n");
                continue;
            }
            int ans=mp[v[x]];
            if(v[x]>a)
                ans--;
            pf("%d\n",ara[ans]);
        }
        ms(ara,0);
    }


    return 0;
}

Light OJ : 1080 – Binary Simulation

0

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1080


/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */
 
#include <bits/stdc++.h>
 
#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d:\n",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long
 
using namespace std;
 
 
/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/
 
/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/
 
struct data
{
    int sum,prop;
};
 
data tree[3*100005];
char str[100005];
 
void update(int n, int b, int e, int i, int j)
{
    if(i>e || j<b) return;
    if(b>=i && e<=j)
    {
//        tree[n].sum+=1;
        tree[n].prop+=1;
        return;
    }
    int l=n*2;
    int r=l+1;
    int mid=(b+e)/2;
    update(l,b,mid,i,j);
    update(r,mid+1,e,i,j);
}
 
void init(int n, int b, int e)
{
    if(b==e)
    {
        tree[n].prop=tree[n].sum=0;
        return;
    }
    int l=n*2;
    int r=l+1;
    int mid=(b+e)/2;
    init(l,b,mid);
    init(r,mid+1,e);
    tree[n].prop=tree[n].sum=0;
}
 
int query(int n, int b, int e, int i, int carry)
{
    if(e<i || b>i) return 0;
    if(b==e && b!=i) return 0;
    if(b==e && b==i)
    {
        return carry+tree[n].prop;
    }
    int l=n*2;
    int r=l+1;
    int mid=(b+e)/2;
    int p1=0,p2=0;
    p1=query(l,b,mid,i,carry+tree[n].prop);
    p2=query(r,mid+1,e,i,carry+tree[n].prop);
    return p1+p2;
}
 
int main()
{
//    CIN;
//    freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    sf(t);
    getchar();
    TEST_CASE(t)
    {
        sc("%s",str+1);
        int l=strlen(str+1);
        int n;
        init(1,1,l);
        sf(n);
        PRINT_CASE;
        while(n--)
        {
            char ch;
            int a,b;
            getchar();
            sc("%c",&ch);
            if(ch=='I')
            {
                sff(a,b);
                update(1,1,l,a,b);
            }
            if(ch=='Q')
            {
                sf(a);
                b=query(1,1,l,a,0);
                if(b & 1)
                {
                    if(str[a]=='0') pf("1\n");
                    else pf("0\n");
                }
                else
                    pf("%c\n",str[a]);
            }
        }
    }
    return 0;
}
 

Light OJ 1080 – Binary Simulation (Segment Tree)

1

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             100010
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d%d",&a,&b)
#define sfff(a,b,c)     scanf("%d%d%d",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d:\n",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

int tree[3*MAX];
char str[MAX];
int n,m;

void init_and_update(int node, int b, int e, int i, int j)
{
    if(b>=i && e<=j)
    {
        tree[node]++;
        return;
    }

    int left=node*2;
    int right=left+1;
    int mid=(b+e)/2;

    if(j<=mid)
        init_and_update(left,b,mid,i,j);
    else if(i>mid)
        init_and_update(right,mid+1,e,i,j);
    else
    {
        init_and_update(left,b,mid,i,mid);
        init_and_update(right,mid+1,e,mid+1,j);
    }
}

int query(int node, int b, int e, int target)
{
    if(b==target && e==target)
    {
        return tree[node];
    }

    int left=node*2;
    int right=left+1;
    int mid=(b+e)/2;

    if(target<=mid)
        return tree[node]+query(left,b,mid,target);
    else
        return tree[node]+query(right,mid+1,e,target);

}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    sf(t);

    TEST_CASE(t)
    {
        ms(tree,0);
        sc("%s",str);
        sf(m);
        n=strlen(str);
        loop(i,n)
            if(str[i]=='1')
            init_and_update(1,1,n,i+1,i+1);

        PRINT_CASE;
        while(m--)
        {
            getchar();
            char ch;
            sc("%c",&ch);
            if(ch=='I')
            {
                int a,b;
                sff(a,b);
                init_and_update(1,1,n,a,b);
            }
            else
            {
                int a;
                sf(a);
                pf("%d\n",query(1,1,n,a)%2);
            }
        }
    }
    return 0;
}