iamSourav's blog

By iamSourav, history, 6 years ago, In English
//problem link : [SEACO](https://www.codechef.com/SEPT17/problems/SEACO/)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 100010
#define mod1 1000000007
struct node1
{
    ll pre,post,lef,rig;
} tree[4*inf+10];
void push_down(ll node,ll type)
{
    if(type)
    {
        tree[2*node].post+=tree[node].post;
        tree[2*node].post=tree[2*node].post%mod1;
        tree[2*node+1].post+=tree[node].post;
        tree[2*node+1].post=tree[2*node+1].post%mod1;
        tree[node].post=0;
    }
    else
    {
        tree[2*node].pre+=tree[node].pre;
        tree[2*node].pre=tree[2*node].pre%mod1;
        tree[2*node+1].pre+=tree[node].pre;
        tree[2*node+1].pre=tree[2*node+1].pre%mod1;
        tree[node].pre=0;
    }
}
void update(ll node,ll l,ll r,ll p,ll q,ll val,ll type)
{
    if(l>q or r<p)
        return;
    if(l>=p and r<=q)
    {
        if(type)
        {
            tree[node].post+=val;
            tree[node].post=tree[node].post%mod1;
        }
        else
        {
            tree[node].pre+=val;
            tree[node].pre=tree[node].pre%mod1;
        }
        return;
    }
    if(type&&tree[node].post)
    {
        push_down(node,type);
    }
    else if(tree[node].pre&&!type)
    {
        push_down(node,type);
    }
    update(2*node,l,(l+r)/2,p,q,val,type);
    update(2*node+1,(l+r)/2+1,r,p,q,val,type);
}
ll query(ll node,ll l,ll r,ll p,ll q,ll type)
{
    if(l>q or r<p)
        return 0;
    if(l>=p and r<=q)
    {
        if(type)
            return tree[node].post;
        else
            return   tree[node].pre;
    }
    if(type&&tree[node].post)
    {
        push_down(node,type);
    }
    else if(tree[node].pre&&!type)
    {
        push_down(node,type);
    }
    return (query(2*node,l,(l+r)/2,p,q,type)+
            query(2*node+1,(l+r)/2+1,r,p,q,type))%mod1;
}
vector<ll>pre,post;
int main()
{
    ll ts,type,l,r;
    scanf("%lld",&ts);
    for(ll t=1; t<=ts; t++)
    {
        memset(tree,0,sizeof tree);
        pre.clear();
        post.clear();
        ll total,cnt;
        scanf("%lld %lld",&total,&cnt);
        for(ll i=1; i<=cnt; i++)
        {
            scanf("%lld %lld %lld",&type,&l,&r);
            tree[i].lef=l;
            tree[i].rig=r;
            if(type==1)
            {
                post.push_back(i);
            }
            else
                pre.push_back(i);
        }
        reverse(pre.begin(),pre.end());
        for(ll i=0; i<pre.size(); i++)
        {
            ll val=query(1,1,total,pre[i],pre[i],0);
            update(1,1,total,tree[pre[i]].lef,tree[pre[i]].rig,(val+1)%mod1,0);
        }
        for(ll i=0; i<post.size(); i++)
        {
            ll val=query(1,1,total,post[i],post[i],0);
            update(1,1,total,tree[post[i]].lef,tree[post[i]].rig,(val+1)%mod1,1);
        }
        for(ll i=1; i<=total; i++)
        {
            printf("%lld ",(query(1,1,total,i,i,1)%mod1));
        }
        printf("\n");
    }
}

Full text and comments »

  • Vote: I like it
  • -16
  • Vote: I do not like it

By iamSourav, history, 7 years ago, In English

I got wrong answer in this problem, but i don't understand where's the problem ?

problem link :(https://www.codechef.com/SNCKPB17/problems/SNELECT)

my code given below:

#include<bits/stdc++.h>
#define pi                  acos(-1)
#define READ                freopen("in.txt", "r", stdin)
#define WRITE               freopen("out.txt", "w", stdout)
#define INF                 1000000000000000000
#define dist(ax,ay,bx,by)   sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by))
#define M                   1000000
#define gcd(a,b)            __gcd(a,b)
#define lcm(a,b)            (a*b)/__gcd(a,b)
#define m_p(a,b)            make_pair(a,b)
#define pb                  push_back
#define pf                  printf
#define sf                  scanf

using namespace std;
typedef unsigned long long llu;
typedef long long lli;
typedef long double ld;

using namespace std;
int main()
{


    string a;

    stack<char>s;
    stack<char>s1;

    lli p,i;
    cin>>p;
    bool mark=true;
    while(p--)
    {
cin>>a;
        mark=true;

        for(i=0; i<a.size(); i++)
        {

            if(a[i]=='m'&&a[i+1]=='s'&&mark)
            {
                mark=false;
                swap(a[i],a[i+1]);
            }

            if(a[i]=='s')
            {
           s.push('s');


            }
            else
            {
                mark=true;

                if(!s.empty()&&a[i-1]=='s') s.pop();
                s1.push('m');

            }



        }



        if(s.size()>s1.size()) cout<<"snakes";
        else  if(s.size()<s1.size()) cout<<"mongooses";
        else cout<<"tie";
        cout<<endl;
        while(!s.empty())
            s.pop();
        while(!s1.empty())
            s1.pop();

}

}

Full text and comments »

  • Vote: I like it
  • -16
  • Vote: I do not like it