Dev And Churu (AUGUST LONG Codechef)

DCGAME.cpp

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
map<long int,long int> mapi,idx;
long int arr[1000005],p;
 
 
void maxHist(long int arr[],long int n)
{
    stack<long int> st;
    long int i=0,maxArea=0,tp;
 
    while(i<n)
    {
        if(st.empty()||arr[i]<=arr[st.top()])
            st.push(i++);
        else
        {
            tp=st.top();
            st.pop();
 
            mapi[arr[tp]]+=(i-tp)*((st.empty()?i:i-st.top()-1)+1)
            -(i-tp)*(i-tp);
 
        }
    }
 
while(!st.empty())
        {
            tp=st.top();
            st.pop();
 
            mapi[arr[tp]]+=(i-tp)*((st.empty()?i:i-st.top()-1)+1)
            -(i-tp)*(i-tp);
 
        }
return;
}
char ansch[1000000005];
 
long int sum[1000005];
int main()
{
    std::ios::sync_with_stdio(0);
 
        long int n,q;
        cin>>n>>q;
 
        for(long int i=0;i<n;i++)
        cin>>arr[i];
 
        maxHist(arr,n);
 
        map<long int,long int>::iterator it;
        long int k=0;
 
        it=mapi.begin();
        sum[0]=(*it).second;
 
        for(;it!=mapi.end();it++)
        {
        arr[k]=(*it).first;
 
        if(k)
        sum[k]=sum[k-1]+(*it).second;
 
        k++;
        }
 
    while(q--)
    {
        char c,D;
 
        long int num;
        cin>>c>>num;
        cin>>D;
 
        long int ind,ans;
 
        ind=lower_bound(arr,arr+k,num)-arr;
 
        if(c=='>')
        {
            if(arr[ind]>num)
            ind--;
 
            if(ind>k-1)
            ans=0;
            else
            ans=sum[k-1]-sum[ind];
        }
        else if (c=='=')
        {
            if(arr[ind]>num)
            ind--;
            else if(arr[ind]<num)
            ind++;
 
            if(ind==0)
            ans=sum[ind];
            else
            ans=sum[ind]-sum[ind-1];
 
            if(arr[ind]!=num)
            ans=0;
 
        }
        else if(c=='<')
        {
            if(arr[ind]>=num)
            ind--;
 
            if(ind==-1)
            ans=0;
            else if(num>arr[k-1])
            ans=sum[k-1];
            else if(ind!=-1)
            ans=sum[ind];
        }
 
       if(D=='D')
        ans++;
 
        if(ans&1)
        ansch[p++]='C';
        else
        ansch[p++]='D';
 
    }
ansch[p++]='\0';
cout<<ansch;
 
}