UVa 11577 Letter Frequency

#include <bits/stdc++.h>
#define LL long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

int main()
{
    int cnt[27];
    int t;
    string s;
    scanf("%d",&t);
    cin.ignore();
    while(t--)
    {
        memset(cnt,0,sizeof cnt);
        getline(cin,s);
        int mx = 0;
        REP(i,SZ(s))
        {
            if((s[i]>='a' and s[i]<='z') or (s[i]>='A' and s[i]<='Z'))
            {
                s[i] = tolower(s[i]);
                int tt = s[i]-'a';
                cnt[tt]++;
                mx = max(mx,cnt[tt]);
            }
        }

        REP(i,27) if(cnt[i]==mx) putchar(i+'a');
        puts("");
    }
    return 0;
}

UVa 10530 Guessing Game

#include <bits/stdc++.h>
#define LL long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

int main()
{
    int n;
    vector <int> th, tl;
    string s;

    while(cin>>n)
    {
        if(n==0) return 0;

        cin.ignore();
        getline(cin,s);

        if(s=="too low")
        {
            tl.push_back(n);
        }
        else if(s=="too high")
        {
            th.push_back(n);
        }
        else
        {
            bool fl = false;

            REP(i,SZ(tl))
            {
                if(n<=tl[i]){fl=true; break;}
            }
            REP(i,SZ(th))
            {
                if(n>=th[i]){fl=true; break;}
            }

            if(fl) puts("Stan is dishonest");
            else puts("Stan may be honest");

            tl.clear(); th.clear();
        }
    }
    return 0;
}

UVa 12570 Keep Rafa At Chelsea

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

int main()
{
    int n,T,cs=0;
    char ch;
    cin>>T;
    while(T--)
    {
        printf("Case %d: ",++cs);
        cin>>n;
        int ls=0, res, fl=0;
        REP(i,n)
        {
            cin>>ch;
            if(ch=='D') ls++;
            else if(ch=='L') ls++;
            else ls=0;

            if(ls>=3 and !fl) {fl=1,res = i+1;}
        }
        if(!fl) puts("Yay! Mighty Rafa persists!");
        else pri(res);
    }
    return 0;
}

UVa 12342 Tax Calculator

#include <bits/stdc++.h>
#define LL long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

LL per(LL n, LL x)
{
    LL res = ceil((double)((n*x)/(100*1.0)));
    return res;
}

int main()
{
    int n,T,cs=0;
    scanf("%d", &T);
    while(T--)
    {
        LL tx = 0;
        printf("Case %d: ", ++cs);

        cin>>n;

        if(n>(180000+300000+400000+300000))
        {
            tx += 0+per(300000,10)+per(400000,15)+per(300000,20)+per(n-(180000+300000+400000+300000),25);
        }
        else if(n>(180000+300000+400000))
        {
            tx += 0+per(300000,10)+per(400000,15)+per(n-(180000+300000+400000),20);
        }
        else if(n>(180000+300000))
        {
            tx += 0+per(300000,10)+per(n-(180000+300000),15);
        }
        else if(n>(180000))
        {
            tx += 0+per(n-(180000),10);
        }
        else tx = 0;

        if(tx>0 and tx<2000) tx=2000;

        pri(tx);
    }
    return 0;
}

UVa 10684 The Jackpot

#include <bits/stdc++.h>
#define LL long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

int main()
{
    int n,a[12345];

    while(cin>>n and n)
    {
        REP(i,n) cin>>a[i];
        LL sm=0,res=0;
        REP(i,n)
        {
            sm += a[i];
            if(sm<=0) sm = 0;
            else res = max(sm,res);
        }
        if(res>0) printf("The maximum winning streak is %lld.\n", res);
        else puts("Losing streak.");
    }
    return 0;
}

SPOJ/LightOJ 1164 Horrible Queries

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
using namespace std;

#define sz 100007
LL a[sz], tr[sz*4], prop[sz*4];

void update(int node, int b, int e, int i, int j, LL val)
{
    if(b>=i and e<=j)
    {
        tr[node] += (e-b+1)*val;
        prop[node] += val;
        return;
    }
    int mid=(b+e)>>1;
    int lft=node<<1 ,rgt=lft+1;

    if(j<=mid) update(lft,b,mid,i,j,val);
    else if(i>mid) update(rgt,mid+1,e,i,j,val);
    else
    {
        update(lft,b,mid,i,j,val);
        update(rgt,mid+1,e,i,j,val);
    }
    tr[node] = tr[lft] + tr[rgt] + prop[node]*(e-b+1);
}

LL query(int node, int b, int e, int i, int j, LL car)
{
    if(b>=i and e<=j)
    {
        return tr[node]+car*(e-b+1);
    }
    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft+1;

    if(j<=mid) query(lft,b,mid,i,j,car+prop[node]);
    else if(i>mid) query(rgt,mid+1,e,i,j,car+prop[node]);
    else
    {
        return (query(lft,b,mid,i,j,car+prop[node]) + query(rgt,mid+1,e,i,j,car+prop[node]));
    }
}

int main()
{
   // freopen("F:\out.txt", "w", stdout);
    int n,qu,T,op,p,q,v,cs=0;
    scanf("%d",&T);
    while(T--)
    {
        memset(tr, 0, sizeof tr);
        memset(prop, 0, sizeof prop);
       // printf("Case %d:\n",++cs);
        scanf("%d%d",&n,&qu);
        REP(i,qu)
        {
            scanf("%d", &op);

            if(op==0)
            {
                scanf("%d%d%d",&p,&q,&v);
                p--,q--;
                update(1,0,n-1,p,q,v);
            }
            else if(op==1)
            {
                scanf("%d%d",&p,&q);
                p--,q--;
                LL res = query(1,0,n-1,p,q,0);
                printf("%lld\n", res);
            }
        }
    }

    return 0;
}

LightOJ 1093 Curious Robinhood

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;
#define sz 100007

int ar[sz],tr[3*sz];

void build(int node, int b, int e)
{
    if(b==e)
    {
        tr[node] = ar[b];
        return;
    }
    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft + 1;
    build(lft,b,mid);
    build(rgt,mid+1,e);
    tr[node] = tr[lft] + tr[rgt];
}

int query(int node, int b, int e, int i, int j)
{
    if(i<=b and j>=e) return tr[node];
    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft + 1;
    if(j<=mid) return query(lft,b,mid,i,j);
    else if(i>mid) return query(rgt,mid+1,e,i,j);
    else return (query(lft,b,mid,i,j) + query(rgt,mid+1,e,i,j));
}

void update(int node, int b, int e, int idx, int val)
{
    if(b==e)
    {
        ar[b] += val;
        tr[node] = ar[b];
        return;
    }

    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft + 1;

    if(idx<=mid) update(lft,b,mid,idx,val);
    else if(idx>mid) update(rgt,mid+1,e,idx,val);
    tr[node] = tr[lft] + tr[rgt];
}


int main()
{
    int T,n,q,x,idx,val,lt,rt,cs=0;
    scanf("%d", &T);
    while(T--)
    {
        printf("Case %d:\n", ++cs);
        scanf("%d%d", &n, &q);

        REP(i,n) scanf("%d", &ar[i+1]);

        build(1,1,n);

        REP(i,q)
        {
            scanf("%d", &x);

            if(x==1)
            {
                scanf("%d", &idx);
                printf("%d\n", ar[idx+1]);
                ar[idx+1] = 0;
                update(1,1,n,idx+1,0);
            }
            else if(x==2)
            {
                scanf("%d%d", &idx, &val);
                update(1,1,n,idx+1,val);
            }
            else if(x==3)
            {
                scanf("%d%d", &lt, &rt);
                printf("%d\n",query(1,1,n,lt+1,rt+1));
            }
        }
    }
    return 0;
}

UVa 12532 Interval Product

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
using namespace std;

#define sz 100007
int a[sz], tr[sz*4];

void build(int node,int b,int e)
{
    if(b==e)
    {
        tr[node] = a[b];
        return;
    }
    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft+1;
    build(lft,b,mid);
    build(rgt,mid+1,e);
    tr[node] = tr[lft] * tr[rgt];
}

int query(int node, int b, int e, int i, int j)
{
    if(i<=b and e<=j) return tr[node];

    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft+1;

    if(j<=mid) return query(lft,b,mid,i,j);
    else if(i>mid) return query(rgt,mid+1,e,i,j);
    else return (query(lft,b,mid,i,j) * query(rgt,mid+1,e,i,j));
}

void update(int node, int b, int e, int idx, int val)
{
    if(b==e)
    {
        a[idx] = val;
        tr[node] = val;
        return;
    }
 
    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft + 1;

    if(idx<=mid)
        update(lft,b,mid,idx,val);
    else if(idx>mid)
        update(rgt,mid+1,e,idx,val);

    tr[node] = tr[lft] * tr[rgt];
}

int main()
{
    int n,q,x,y;
    char ch;
    string tst;

    while(cin>>n>>q)
    {
        tst = "";

        REP(i,n)
        {
            cin>>x;

            if(x>0) x=1;
            else if(x<0) x=-1;

            a[i+1] = x;
        }

        build(1,1,n);

        REP(i,q)
        {
            cin>>ch;
            if(ch=='C')
            {
                int idx,val;
                cin>>idx>>val;

                if(val>0) val = 1;
                else if(val<0) val = -1;

                update(1,1,n,idx,val);
            }
            else if(ch=='P')
            {
                cin>>x>>y;
                int res = query(1,1,n,x,y);
                if(res==0) tst+="0";
                else if(res>0) tst+="+";
                else tst+="-";
            }
        }
        pri(tst);
    }
    return 0;
}

UVa 11235 Frequent Values

#include <bits/stdc++.h>
#define LL long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

#define sz 100007
int a[sz], ltfrq[sz], rtfrq[sz], tr[4*sz];

void build(int node, int b, int e)
{
    if(b==e)
    {
        tr[node] = ltfrq[b];
        return;
    }
    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft+1;
    build(lft,b,mid);
    build(rgt,mid+1,e);
    tr[node] = max(tr[lft], tr[rgt]);
}

int query(int node, int b, int e, int i, int j)
{
    if(b>=i and e<=j) return tr[node];

    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft+1;

    if(j<=mid) return query(lft,b,mid,i,j);
    else if(i>mid) return query(rgt,mid+1,e,i,j);
    else return max(query(lft,b,mid,i,j), query(rgt,mid+1,e,i,j));
}

int main()
{
    int n,q,l,r,res;
    while(scanf("%d", &n)==1 and n!=0)
    {
        scanf("%d",&q);
        REP(i,n) scanf("%d",&a[i+1]);

        ltfrq[1] = 1;
        FOR(i,2,n)
        {
            if(a[i]==a[i-1]) ltfrq[i] = ltfrq[i-1] + 1;
            else ltfrq[i] = 1;
        }

        rtfrq[n] = n;
        for(int i=n-1; i>=1; i--)
        {
            if(a[i]==a[i+1]) rtfrq[i] = rtfrq[i+1] + 1;
            else rtfrq[i] = 1;
        }

        build(1,1,n);

        REP(i,q)
        {
            scanf("%d%d",&l,&r);
         
            if(a[l]==a[r]) res = r-l+1;
            else
            {
                res = max(rtfrq[l],query(1,1,n,l+rtfrq[l],r));
            }
            printf("%d\n", res);
        }
    }
    return 0;
}

UVa 10608 - Friends

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

// maximum nodes in a connected subgraph

vector<int>adj[30007];
int vis[30007];
int cnt;

void dfs(int u)
{
    vis[u]=1;
    cnt++;
    REP(i,SZ(adj[u]))
    {
        if(vis[adj[u][i]]==0) dfs(adj[u][i]);
    }
}

int main()
{
    int T, n, m, u, v;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        FOR(i,1,m)
        {
            cin>>u>>v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        int mx=0;
        memset(vis, 0, sizeof vis);
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                cnt=0;
                dfs(i);
                mx=max(mx, cnt);
            }
        }
        pri(mx);

       FOR(i,1,n) adj[i].clear();
    }
    return 0;
}



// disjoint sets solution .. gotta take care of the pair counting -_-

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

int par[30000];

void init(int node)
{
    REP(i,node) par[i] = i;
}

int find(int r)
{
    return par[r]==r ? r : par[r] = find(par[r]);
}

void make_union(int a,int b)
{
    int u=find(a), v=find(b);

    if(u != v)
        par[u]=v;
}

int main()
{
    int T,node,edge,u,v;

    cin>>T;

    while(T--)
    {
        cin>>node>>edge;

        init(node);

        REP(i,edge)
        {
            cin>>u>>v;
            make_union(u,v);
        }

        REP(i,node) find(i);

        REP(i,node) prii(i,par[i]);

        int cnt,mx = -1;

        REP(i,node)
        {
            cnt = 1;   //*********
            FOR(j,i+1,node-1)
            {
                if(par[i] == par[j]) cnt++;      //*********
            }
            mx = max(mx,cnt);
        }

        pri(mx);
    }
    return 0;
}

UVa 459 - Graph Connectivity

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

map<char,char> par;

char findr(char ch)
{
    if(par[ch]=='\0') return ch;

    char x = findr(par[ch]);
    par[ch]= x;
    return x;
}

int main()
{
    ll tc;
    string s;
    char ch;
    bool fl = 0;
    int mx = 1;
    scl(tc);
    while(tc--)
    {
        par.clear();

        if(fl) printf("\n");
        fl=1;

        cin>>s;
        ch = s[0];

        getchar();

        while(getline(cin,s) and s!="")
        {
            char ch1 = s[0], ch2 = s[1];
            char u = findr(ch1), v = findr(ch2);
            if(u!=v) par[v] = u;
        }
        int cnt = 0;
        FOR(i,(int)'A',ch)
        {
            if(par[i]=='\0') cnt++;
        }
        printf("%d\n", cnt);
    }
    return 0;
}