CodeForces 52C Circular RMQ

Problem Statement, Tag: Segment Tree

#include<bits/stdc++.h>
using namespace std;

#define MX 200005

vector<int> parse(string str)
{
    vector<int>res;
    int s;
    istringstream os(str);
    while(os>>s)
        res.push_back(s);
    return res;
}

int mn[MX*4], lazy_value[4*MX];

void update_node(int idx, int st, int ed, int val)
{
    lazy_value[idx]+=val;
    mn[idx]+=val;
return;
}

void update_lazy(int idx, int st, int ed)
{
    if(st==ed)    return;

    int mid=(st+ed)>>1, lft=idx<<1, rgt=lft | 1;

    update_node(lft, st, mid, lazy_value[idx]);
    update_node(rgt, mid+1, ed, lazy_value[idx]);
    lazy_value[idx]=0;
}

void insert(int idx, int st, int ed, int s, int e, int val)
{
    if(st==s && ed==e)
    {
        update_node(idx, st, ed, val);
        return;
    }

    if(lazy_value[idx]) update_lazy(idx, st, ed);

    int mid=(st+ed)>>1, lft=idx<<1, rgt=lft | 1;
    if(e<=mid) insert(lft, st, mid, s, e, val);
    else if(s>mid) insert(rgt, mid+1, ed, s, e, val);
    else
    {
        insert(lft, st, mid, s, mid, val);
        insert(rgt, mid+1, ed, mid+1, e, val);
    }
    mn[idx]=min(mn[lft], mn[rgt]);
return;
}

int query(int idx, int st , int ed, int s, int e)
{
    if(st==s && ed==e) return mn[idx];
    if(lazy_value[idx]) update_lazy(idx, st, ed);

    int mid=(st+ed)>>1, lft=idx<<1, rgt=lft | 1;
    if(mid>=e)  return query(lft, st, mid, s, e);
    else if(s>mid)  return query(rgt, mid+1, ed, s, e);
    else  return min(query(lft, st, mid, s, mid), query(rgt, mid+1, ed, mid+1, e));
}

int main()
{
    int n, x;
    string s;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        insert(1, 1, n, i, i, x);
    }
    cin>>x;
    getline(cin, s);
    while(x--)
    {
        getline(cin, s);
        vector<int>v;
        v=parse(s);
        v[0]++;
        v[1]++;
        if(v.size()==3)
        {
            if(v[0]<=v[1]) insert(1, 1, n, v[0], v[1], v[2]);
            else insert(1, 1, n, v[0], n, v[2]), insert(1, 1, n, 1, v[1], v[2]);
        }
        else
        {
            if(v[0]<=v[1]) cout<<query(1, 1, n, v[0], v[1])<<endl;
            else cout<<min(query(1, 1, n, v[0], n), query(1, 1, n, 1, v[1]))<<endl;
        }
    }
return 0;
}

UVa 10594 - Data Flow Solution

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / hackerrank / uva / uvalive, spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010


struct Edge
{
    int u, v, next;
    long long cost, cap;
} e[5002*4];  //maximum edge = 5000

int source, sink,  edgenum, first[102], par[102];   //maximum node = 100
long long tData, dist[102], C;

void addEdge( int u, int v, long long c, long long f)
{
    e[edgenum].u = u;
    e[edgenum].v = v;
    e[edgenum].cost = c;
    e[edgenum].cap = f;
    e[edgenum].next = first [u];
    first[u] = edgenum;
    edgenum++;
}

void SPFA(int node)
{
    queue < int > q;
    int vis[node+2];

    for ( int i = 0 ; i <= node; i++)    dist[i] = LLONG_MAX;
    CLR(vis);
    SET(par);
    dist[source] = 0;
    vis[source] = 1 ;



    q.push (source);
    while (!q.empty ())
    {
        int u = q.front();
        vis[u] = 0 ;
        q.pop ();
        for ( int k = first[u]; k != - 1 ; k = e[k].next)
        {
            int v = e[k].v;
            if (e[k].cap && (dist[u] + e[k].cost) < dist[v])
            {
                par[v] = k;
                dist[v] = dist[u] + e[k].cost;
                if (!vis[v])
                {
                    vis[v] = 1 ;
                    q.push (v);
                }
            }
        }
    }
    return;
}

int mincost_maxflow (int node)
{
    long long F=0, mn;
    C=0;
    while ( 1 )
    {
        SPFA (node);
        if (dist[sink] == LLONG_MAX)   break ;
        mn= LLONG_MAX;
        for ( int k = par[sink]; k != - 1 ; k = par[e[k].u])
            mn=min(mn, e[k].cap);
        for ( int k = par[sink]; k != - 1 ; k = par[e[k].u])
        {
            e[k].cap -= mn;
            e[k^1].cap += mn;
        }
        F += mn;   //nessary change if F given
        C += mn * dist [sink];
    }
    return F;
}

int main ()
{
    int node, edge,  u, v;
    long long cap;
    while(scanf("%d%d", &node, &edge)==2)
    {
        int u[edge+2], v[edge+2];
        long long  cost[edge+2];
        for ( int i = 0 ; i < edge; i ++)
            scanf ( "%d%d%lld" , &u[i], &v[i], &cost[i]);
        scanf ( "%lld%lld" , &tData, &cap);
        edgenum = 0 ;
        SET(first);
        for ( int i = 0 ; i < edge; i ++)
        {
            addEdge (u[i], v[i],  cost[i], cap);
            addEdge (v[i], u[i], -cost[i], 0 );
            addEdge (v[i], u[i],  cost[i], cap);
            addEdge (u[i], v[i], -cost[i], 0 );
        }

        addEdge(0, 1, 0, tData);
        addEdge(1, 0, 0, 0);

        source = 0 ;
        sink = node;
        long long res = mincost_maxflow (node);
        if (res==tData)
            printf ( "%lld\n" , C);
        else
            printf ( "Impossible.\n" );
    }
    return  0 ;
}