1111 - Best Picnic Ever

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

Solution :

#include<bits/stdc++.h>

using namespace std;
vector<int>v[1002];
vector<int>vv;
int visited[1002];

int arr[1002];

void bfs(int s)
{
    queue<int>q;
    memset(visited,-1,sizeof(visited));
    visited[s]=0;
    arr[s]=arr[s]+1;
    q.push(s);

    int u,p,x;

    while(!q.empty())
    {
        u=q.front();
        q.pop();
        for(int i=0; i<v[u].size(); i++)
        {
            p=v[u][i];
            if(visited[p]==-1)
            {
                visited[p]=visited[u]+1;
                x=arr[p]=arr[p]+1;
                q.push(p);

            }
        }

    }
    //w= visited[d]-visited[s];
    //return w;
}

int main()
{
    int t,n,m,k,a,b;

    scanf("%d",&t);

    for(int ca=1; ca<=t; ca++)
    {
        scanf("%d%d%d",&k,&n,&m);

        for(int i=1; i<=k; i++)
        {
            scanf("%d",&a);
            vv.push_back(a);
        }
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&a,&b);
            v[a].push_back(b);
        }
        for(int i=0; i<k; i++)
        {
            bfs(vv[i]);

        }
        for(int i=0; i<1002; i++) v[i].clear();
        int cnt=0;

        for(int i=1; i<=n; i++ )
        {
            if(arr[i]==k) cnt++;
        }

        printf("Case %d: %d\n",ca,cnt);

        vv.clear();
        memset(arr,0,sizeof(arr));
    }

}

1093 - Ghajini

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

Solution :

#include<bits/stdc++.h>

#define mix 100002

using namespace std;


int arr[mix];

struct Node
{
    int mn;
    int mx;
}  tree[mix*4];



void init(int node, int b,int e)
{

    if(b==e)
    {
        tree[node].mn=arr[b];
        tree[node].mx=arr[b];
        return;
    }

    int left=2*node;
    int right=(2*node )+1;

    int mid=(b+e)/2;

    init(left,b,mid);
    init(right,mid+1,e);

    tree[node].mn=min(tree[left].mn,tree[right].mn);
    tree[node].mx=max(tree[left].mx,tree[right].mx);

}

Node query(int node,int b,int e,int i,int j)
{
    if(j<b || i>e)
    {

        Node temp;
        temp.mn=1000000000;
        temp.mx=-1;
        return temp ;
    }

    if(b>=i && e<=j)
    {

        return tree[node];
    }

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

    Node p1=query(left,b,mid,i,j);
    Node p2=query(right,mid+1,e,i,j);


    Node p3;
    p3.mx=max(p1.mx,p2.mx);
    p3.mn=min(p1.mn,p2.mn);

    return p3;
}




int main()
{


    int t,n,d;
    Node temp;
    int ans;

    scanf("%d",&t);

    for(int ca=1;ca<=t;ca++)
    {
        scanf("%d%d",&n,&d);

        for(int i=1;i<=n;i++) scanf("%d",&arr[i]);

        init(1,1,n);

        ans=0;

        for(int i=1;i+d-1<=n;i++)
        {
           temp=query(1,1,n,i,i+d-1);
           ans=max(ans,temp.mx-temp.mn);

        }
        printf("Case %d: %d\n",ca,ans);
    }
}

1083 - Histogram

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

Solution :

#include<bits/stdc++.h>

#define mx 100001

using namespace std;


int arr[mx];

struct Node
{
    int val;
    int index;
}  tree[mx*4];

vector<int>v;

void init(int node, int b,int e)
{
    int c,d;

    if(b==e)
    {
        c=tree[node].val=arr[b];
        d=tree[node].index=b;
        return;
    }

    int left=2*node;
    int right=(2*node )+1;

    int mid=(b+e)/2;

    init(left,b,mid);
    init(right,mid+1,e);


    if(tree[left].val<tree[right].val)
    {
        c=tree[node].val=tree[left].val;
        d=tree[node].index=tree[left].index;
    }
    else
    {
        c=tree[node].val=tree[right].val;
        d=tree[node].index=tree[right].index;
    }


}

Node query(int node,int b,int e,int i,int j)
{
    if(j<b || i>e)
    {

        Node temp;
        temp.val=9000000;
        temp.index=-1;
        return temp ;
    }

    if(b>=i && e<=j)
    {

        return tree[node];
    }

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

    Node p1=query(left,b,mid,i,j);
    Node p2=query(right,mid+1,e,i,j);

    if(p1.val<p2.val) return p1;
    else return p2;
}




int main()
{


    int t,n,q,l,r,ans,mn,L,R;
    scanf("%d",&t);
    Node temp;
    for(int ca=1; ca<=t; ca++)
    {


        scanf("%d",&n);

        for(int i=1; i<=n; i++) scanf("%d",&arr[i]);


        init(1,1,n);

        temp=query(1,1,n,1,n);
        ans=temp.val;
        mn=ans;
        ans=n*ans;

        int mid=temp.index;

        l=1;
        r=mid-1;
        L=mid+1;
        R=n;

        if(l<=r)
        {
            v.push_back(l);
            v.push_back(r);
        }
        if(L<=R)
        {
            v.push_back(L);
            v.push_back(R);
        }


        while(v.size())
        {

            temp=query(1,1,n,v[0],v[1]);
            mn=(v[1]-v[0]+1)*temp.val;
            ans=max(mn,ans);
            mid=temp.index;
            l=v[0];
            r=mid-1;
            L=mid+1;
            R=v[1];

            if(l<=r)
            {
                v.push_back(l);
                v.push_back(r);
            }
            if(L<=R)
            {
                v.push_back(L);
                v.push_back(R);
            }

            v.erase(v.begin()+0);
            v.erase(v.begin()+0);
        }




        printf("Case %d: %d\n",ca,ans);
        v.clear();

    }

}

1112 - Curious Robin Hood

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

Solution :

#include<bits/stdc++.h>

#define mx 100001

using namespace std;


int arr[mx];
int tree[mx*4];
int global;

void init(int node, int b,int e)
{
    if(b==e)
    {
        tree[node]=arr[b];
        return;
    }

    int left=2*node;
    int right=(2*node )+1;

    int mid=(b+e)/2;

    init(left,b,mid);
    init(right,mid+1,e);

    tree[node]=(tree[left]+tree[right]);


}

int query(int node,int b,int e,int i,int j)
{
    if(j<b || i>e) return 0;

    if(b>=i && e<=j)
    {
        return tree[node];
    }

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

    int p1=query(left,b,mid,i,j);
    int p2=query(right,mid+1,e,i,j);

    return p1+p2;
}

void update(int node,int b,int e,int i,int val)
{
    if(i<b || i>e) return ;

    if(b==e)
    {
        global=tree[node];

        tree[node]=val;
        return ;
    }

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

    update(left,b,mid,i,val);
    update(right,mid+1,e,i,val);

    tree[node]=tree[left]+tree[right];
}

void update1(int node,int b,int e,int i,int val)
{
    if(i<b || i>e) return ;

    if(b==e)
    {
        global=tree[node];

        tree[node]=global+val;
        return ;
    }

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

    update1(left,b,mid,i,val);
    update1(right,mid+1,e,i,val);

    tree[node]=tree[left]+tree[right];
}



int main()
{

    int t,n,q,l,r,ans,v;
    scanf("%d",&t);

   for(int ca=1;ca<=t;ca++)
   {


       scanf("%d%d",&n,&q);

       for(int i=1;i<=n;i++) scanf("%d",&arr[i]);


       init(1,1,n);



       printf("Case %d:\n",ca);

       for(int i=1;i<=q;i++)
       {
           scanf("%d",&l);

           if(l==1)
           {
               scanf("%d",&r);
               update(1,1,n,r+1,0);
                printf("%d\n",global);
           }
           else if(l==2)
           {
               scanf("%d%d",&r,&v);

               update1(1,1,n,r+1,v);

           }
           else if(l==3)
           {
               scanf("%d%d",&r,&v);
               ans=query(1,1,n,r+1,v+1);
           printf("%d\n",ans);

           }


       }


   }

}

1082 - Array Queries

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

Solution :

#include<bits/stdc++.h>

#define mx 100001

using namespace std;


int arr[mx];
int tree[mx*4];


void init(int node, int b,int e)
{
    if(b==e)
    {
        tree[node]=arr[b];
        return;
    }

    int left=2*node;
    int right=(2*node )+1;

    int mid=(b+e)/2;

    init(left,b,mid);
    init(right,mid+1,e);

    tree[node]=min(tree[left],tree[right]);


}

int query(int node,int b,int e,int i,int j)
{
    if(j<b || i>e) return mx;

    if(b>=i && e<=j)
    {
        return tree[node];
    }

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

    int p1=query(left,b,mid,i,j);
    int p2=query(right,mid+1,e,i,j);

    return min(p1,p2);
}



int main()
{

    int t,n,q,l,r,ans;
    scanf("%d",&t);

   for(int ca=1;ca<=t;ca++)
   {


       scanf("%d%d",&n,&q);

       for(int i=1;i<=n;i++) scanf("%d",&arr[i]);


       init(1,1,n);



       printf("Case %d:\n",ca);

       for(int i=1;i<=q;i++)
       {
           scanf("%d%d",&l,&r);
           ans=query(1,1,n,l,r);
           printf("%d\n",ans);
       }


   }

}

Segment Tree Source Code

Tutorial : http://www.shafaetsplanet.com/planetcoding/?p=1557


#include<bits/stdc++.h>

#define mx 100001

using namespace std;


int arr[mx];
int tree[mx*4];


void init(int node, int b,int e)
{
    if(b==e)
    {
        tree[node]=arr[b];
        return;
    }

    int left=2*node;
    int right=(2*node )+1;

    int mid=(b+e)/2;

    init(left,b,mid);
    init(right,mid+1,e);

    tree[node]=tree[left]+tree[right];


}

int query(int node,int b,int e,int i,int j)
{
    if(j<b || i>e) return 0;

    if(b>=i && e<=j)
    {
        return tree[node];
    }

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

    int p1=query(left,b,mid,i,j);
    int p2=query(right,mid+1,e,i,j);

    return p1+p2;
}

void update(int node,int b,int e,int i,int val)
{
    if(i<b || i>e) return;

    if(b==e)
    {
        tree[node]=val;
        return;
    }

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

    update(left,b,mid,i,val);
    update(right,mid+1,e,i,val);

    tree[node]=tree[left]+tree[right];
}

int main()
{
    int n;
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&arr[i]);
    }

    init(1,1,n);

    cout<<query(1,1,n,3,7)<<endl;
    update(1, 1, n, 2, 2);
    cout << query(1, 1, n, 1, 2) << endl;
}

UVA 10114 - Loansome Car Buyer

Problem Link : https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=1055&m


Solve:

#include<bits/stdc++.h>

using namespace std;

map<int,float>mp;

int main()
{


    int a,d,e,ans;
    float b,c,f,dr;
    float carv=0,own=0;

    while(1)
    {
        scanf("%d%f%f%d",&a,&b,&c,&d);

        if(a<0) break;

        mp.clear();
        ans=0;

        for(int i=1; i<=d; i++)
        {
            scanf("%d%f",&e,&f);
            mp[e]=f;
        }

        own=c;
        carv=b+c;
        b=c/a;
        for(int i=0; i<=a; i++)
        {
            if(mp[i]==0)
            {
                mp[i]=mp[i-1];
            }

            carv=carv-(carv*mp[i]);
            own=c-(i*b);

            if(carv>own)
            {
                ans=i;
                break;
            }

        }
        if(ans!=1) printf("%d months\n",ans);
        else printf("%d month\n",ans);
    }

}