Category Archives: SPOJ

(Spoj) 6256. Inversion Count (INVCNT)

0
Posted on by 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl

using namespace std;

#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;
struct ASDFG{
    template<typename T>
    ASDFG& operator,(vector<T> &v){
        pf("[");
        cout<<v[0];
        FOR(i, 1, SZ(v)){
            cout<<", "<<v[i];
        }
        pf("]");
        return *this;
    }

    template<typename T>
    ASDFG& operator,(T x) {
        cout<<x<<" ";
        return *this;
    }


}asdfg;



//Header ends here

#define MAXX 10000002
#define lowBit(x) (x & -(x))


int tree[MAXX];


void update(int pos, int val)
{
    while(pos<= MAXX)
    {
        tree[pos] += val;
        pos = pos + lowBit(pos);
    }
}

ll get(int pos)
{
    ll sum = 0;
    while(pos>0)
    {
        sum += tree[pos];
        pos -= lowBit(pos);
    }
    return sum;
}


int main()
{
    int ara[200000+2];
    int kases;

    take(kases);

    int n;

    while(kases--)
    {
        mem(tree, 0);
        ll res = 0;
        take(n);

        loop(i, n)
        {
            take(ara[i]);
        }

        for(int i=n-1; i>-1; i--)
        {
            update(ara[i], 1);
            res += get(ara[i]-1);
        }

        cout<<res<<endl;


    }


}

(SPOJ) 8425. Coloring Trees

0
Posted on by 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl

using namespace std;


#define MAXX 100002
char color[MAXX];
int parent[MAXX];
vector<int>graph[MAXX];


int find(int u)
{
    if(parent[u] == u) return u;
    return parent[u] = find(parent[u]);
}

int main()
{
    int N;
    int x, a, b;
    sf("%d", &N);
    loop(i, N)
    {
        color[i] = -1;
        parent[i] = i;
    }
    N--;
    loop(i, N)
    {
        sf("%d %d", &a, &b);
        graph[a].pb(b);
        graph[b].pb(a);
    }

    int Q;
    sf("%d", &Q);

    loop(i, Q)
    {
        sf("%d %d %d", &x, &a, &b);
        if(x == 1)
        {
            color[a] = b;
            loop(i, SZ(graph[a]))
            {
                if(color[graph[a][i]] == b)
                {
                    parent[find(a)] = find(graph[a][i]);
                }
            }
        }
        else if(x==2)
        {
            if(find(a) == find(b))
            {
                if(a!=b || color[a] != -1 )
                    pf("YES\n");
                else
                    pf("NO\n");
            }

            else
                pf("NO\n");
        }
    }
    return 0;
}

(SPOJ) 61. Brackets

0
Posted on by 
//link: http://www.spoj.com/problems/BRCKTS/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl

using namespace std;

#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;
struct ASDFG{
    template<typename T>
    ASDFG& operator,(vector<T> &v){
        pf("[");
        cout<<v[0];
        FOR(i, 1, SZ(v)){
            cout<<", "<<v[i];
        }
        pf("]");
        return *this;
    }

    template<typename T>
    ASDFG& operator,(T x) {
        cout<<x<<" ";
        return *this;
    }


}asdfg;



//Header ends here

struct DATA
{
    int needed_opening;
    int needed_closing;
    DATA()
    {
        needed_closing = needed_opening = 0;
    }
};

#define MAXX 30002

DATA sum[4*MAXX];
char str[MAXX];


void insert(int idx, int st, int ed)
{
    if(st == ed)
    {

        if(str[st] == '(')
        {
            sum[idx].needed_closing = 1;
            sum[idx].needed_opening = 0;
        }
        else
        {
            sum[idx].needed_opening = 1;
            sum[idx].needed_closing = 0;
        }
    }
    else
    {
        int l = idx*2;
        int r = l +1;
        int mid = (st+ed)/2;

        insert(l, st, mid);
        insert(r, mid+1, ed);

        int r_closing_min = min(sum[l].needed_closing, sum[r].needed_opening);

        sum[idx].needed_closing = sum[l].needed_closing - r_closing_min + sum[r].needed_closing;

        sum[idx].needed_opening = sum[r].needed_opening - r_closing_min + sum[l].needed_opening;
    }
}

void update(int idx, int st, int ed, int pos)
{
    if(st == ed)
    {
        if(str[pos] == '(')
        {
            sum[idx].needed_closing--;
            sum[idx].needed_opening++;
            str[pos] = ')';
        }
        else
        {
            sum[idx].needed_closing++;
            sum[idx].needed_opening--;
            str[pos] = '(';
        }
    }
    else
    {
        int l = idx*2;
        int r = l + 1;
        int mid = (st+ed)/2;
        if(pos <= mid)
        {
            update(l, st, mid, pos);
        }
        else
        {
            update(r, mid+1, ed, pos);
        }


        int r_closing_min = min(sum[l].needed_closing, sum[r].needed_opening);

        sum[idx].needed_closing = sum[l].needed_closing - r_closing_min + sum[r].needed_closing;

        sum[idx].needed_opening = sum[r].needed_opening - r_closing_min + sum[l].needed_opening;
    }
}

int main()
{
    int stlen, m, k;

    loop(kaseno, 10)
    {
        pf("Test %d:\n", kaseno+1);
        sf("%d", &stlen);
        stlen--;
        sf("%s", str);
        insert(1, 0, stlen);


        sf("%d", &m);
        loop(i, m)
        {
            sf("%d", &k);
            if(k == 0)
            {
                if(sum[1].needed_closing == 0 && sum[1].needed_opening == 0)
                {
                    pf("YES\n");
                }
                else
                {
                    pf("NO\n");
                }
            }
            else
            {
                update(1, 0, stlen, k-1);
            }
        }
    }



    return 0;
}

(SPOJ) 1043. Can you answer these queries I

0
Posted on by 
/*
user: hasib
link: http://www.spoj.com/problems/GSS1/
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>

#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<sstream>


#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define mem(a, v) memset(a, v, sizeof(a))
#define pb push_back
#define sf scanf
#define pf printf
#define getint(a) sf("%d", &a)
#define INF 1<<29
#define SZ(v) int(v.size())
#define pi acos(-1.0)
#define all(v) v.begin(), v.end()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define ll long long
#define debug cout<<"came here"<<endl

using namespace std;

#define MAXX 50002

int cnt;


struct DATA{
    int prefixsum, suffixsum, fullsum, maxsum;
};

DATA sum[4*MAXX];


DATA merge(DATA a, DATA b)
{
    DATA result;

    result.fullsum = a.fullsum + b.fullsum;


    result.maxsum = max( a.maxsum, b.maxsum );
    result.maxsum = max( result.maxsum, a.suffixsum + b.prefixsum );

    result.prefixsum = max( a.prefixsum, a.fullsum + b.prefixsum  );

    result.suffixsum = max(b.suffixsum, b.fullsum + a.suffixsum);


    return result;
}




void insert_update(int idx, int st, int ed, int pos, int value)
{
    if(st == pos && pos == ed)
    {

        sum[idx].fullsum = sum[idx].maxsum  = sum[idx].prefixsum = sum[idx].suffixsum = value;
        return;
    }


    int l = idx<<1;
    int r = l + 1;
    int mid = (st + ed)/2;


    if(pos <= mid)
    {
        insert_update(l, st, mid, pos, value);
    }
    else
    {
        insert_update(r, mid+1, ed, pos, value);
    }

    sum[idx] = merge(sum[l], sum[r]);
}


DATA quer(int idx, int st, int ed, int i, int j)
{
    if(st == i && ed == j) return sum[idx];

    int l = idx<<1;
    int r = l + 1;
    int mid = (st + ed)/2;

    if(j <= mid)
    {
        return quer(l, st, mid, i, j);
    }
    else if( i> mid)
    {
        return quer(r, mid+1, ed, i, j);
    }
    else
    {
        return merge( quer(l, st, mid, i, mid), quer(r, mid+1, ed, mid+1, j) );
    }


}

int main()
{
    //read();
    DATA result;
    getint(cnt);
    int num;
    for(int i=1; i<=cnt; i++)
    {
        getint(num);
        insert_update(1, 1, cnt, i, num);
    }

    int m;
    getint(m);
    int p, q;
    loop(i, m)
    {
        getint(p); getint(q);

        result = quer(1, 1, cnt, p, q);
        pf("%d\n", result.maxsum);
    }
    return 0;


}

(SPOJ) 1805. Largest Rectangle in a Histogram

0
Posted on by 
/*
user: hasib
time: 0.200 sec
link: http://www.spoj.com/problems/HISTOGRA/
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 100000000
#define mod abs
#define pf printf
#define sf scanf

using namespace std;

#define MAXX 100005

int height[MAXX];
int n;





int main()
{
    ll left[MAXX], right[MAXX];
    ll result;
    while(true)
    {
        getint(n);
        if(n == 0) break;


        height[0] = -1;

        for(int i=1; i<=n; i++)
        {
            getint(height[i]);
        }

        height[n+1] = -1;

        {
            stack<int>sk;
            sk.push(0);
            for(int i=1; i<=n; i++)
            {
                while( height[sk.top()] >= height[i] )
                {
                    sk.pop();
                }
                left[i] = i - sk.top();
                sk.push(i);

            }
        }

        {


            stack<int>st;
            st.push(n+1);

            for(int i = n; i>0; i--)
            {
                while(height[st.top()] >= height[i] )
                {
                    st.pop();
                }
                right[i] = st.top() - i;
                st.push(i);

            }
        }

        result = -INF;

        for(int i=1; i<=n; i++)
        {
            result = max(result, (left[i] + right[i]-1) * height[i]) ;
        }
        cout<<result<<endl;
    }


}

(SPOJ) 345. Mixtures

0
Posted on by 
/*
user: hasib
time: 0.07 sec
link: http://www.spoj.com/problems/MIXTURES/
*/


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>

#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<sstream>


#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define mem(a, v) memset(a, v, sizeof(a))
#define pb push_back
#define sf scanf
#define pf printf
#define getint(a) sf("%d", &a)
#define INF 1<<29
#define SZ(v) int(v.size())
#define pi acos(-1.0)
#define all(v) v.begin(), v.end()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)

using namespace std;


#define MAXX 101
#define type int




int number_of_color;
int colors[MAXX];

type dp[MAXX][MAXX];
int new_color[MAXX][MAXX];

type rec(int s, int e)
{


    type &ret = dp[s][e];
    if(ret != -1) return ret;


    if(s + 1 == e )
    {
        new_color[s][e] = (colors[s] + colors[e]) % 100;
        return ret = (colors[s] * colors[e]);
    }
    else if(s==e)
    {
        new_color[s][e] = colors[s];
        return ret = 0;
    }


    ret = INF;


    for(int i=s; i<e; i++)
    {
        rec(s, i);
        rec(i+1, e);
        if( rec(s, i) + rec(i+1, e) + (new_color[s][i] * new_color[i+1][e]) < ret )
        {
            new_color[s][e] = (new_color[s][i] + new_color[i+1][e]) % 100;
            ret = rec(s, i) + rec(i+1, e) + (new_color[s][i] * new_color[i+1][e]);
        }
    }

    return ret;
}






int main()
{
    while(getint(number_of_color) == 1)
    {
        loop(i, number_of_color)
        {
            getint(colors[i]);
        }
        mem(dp, -1);
        cout<<rec(0, number_of_color - 1)<<endl;
    }

    return 0;



}