Getting Wa in codechef problem from sep17 long can't find any test case

Правка en1, от iamSourav, 2018-05-12 18:18:19
//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");
    }
}

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский iamSourav 2018-05-12 18:20:13 40
en1 Английский iamSourav 2018-05-12 18:18:19 3180 Initial revision (published)