Submission #426318

#	Time	Username	Problem	Language	Result	Execution time	Memory
426318		TLP39	Progression (NOI20_progression)	C++14	55 / 100	1657 ms	100228 KiB

Progression

#include <stdio.h>
#include <math.h>
#include <utility>
#include <string.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
typedef long long int ll;
struct dev{
    bool typ;
    ll s,c;
};

struct play{
    ll l,r,len,cl,dl,cr,dr,c;
};

dev rep(dev x,dev y)
{
    if(y.typ) return y;
    return {x.typ,x.s+y.s,x.c+y.c};
}

play mix(play x,play y)
{
    play ans={x.l,y.r,x.len+y.len,x.cl,x.dl,y.cr,y.dr,max(x.c,y.c)};
    if(x.cl==x.len)
    {
        if(x.len==1)
        {
            ans.dl=y.l-x.r;
            if(y.cl==1) ans.cl=2;
            else
            {
                if(y.dl==y.l-x.r) ans.cl=y.cl+1;
                else ans.cl=2;
            }
        }
        else
        {
            if(y.l-x.r!=x.dl) ans.cl=x.cl;
            else
            {
                if(y.dl==x.dl) ans.cl=x.cl+y.cl;
                else ans.cl=x.cl+1;
            }
        }
    }

    if(y.cr==y.len)
    {
        if(y.len==1)
        {
            ans.dr=y.l-x.r;
            if(x.cr==1) ans.cr=2;
            else
            {
                if(x.dr==y.l-x.r) ans.cr=x.cr+1;
                else ans.cr=2;
            }
        }
        else
        {
            if(y.l-x.r!=y.dr) ans.cr=y.cr;
            else
            {
                if(x.dr==y.dr) ans.cr=x.cr+y.cr;
                else ans.cr=y.cr+1;
            }
        }
    }

    if(y.l-x.r==x.dr)
    {
        if(y.l-x.r==y.dl)
        {
            ans.c=max(ans.c,x.cr+y.cl);
        }
        else
        {
            ans.c=max(ans.c,x.cr+1);
        }
    }
    else
    {
        if(y.l-x.r==y.dl)
        {
            ans.c=max(ans.c,1+y.cl);
        }
        else
        {
            ans.c=max(ans.c,2ll);
        }
    }

    return ans;
}

play mod(play x,dev y,ll l,ll r)
{
    play ans=x;
    if(y.typ)
    {
        ans.l=y.s+(l-1)*y.c;
        ans.r=y.s+(r-1)*y.c;
        ans.cl=ans.len;
        ans.cr=ans.len;
        ans.c=ans.len;
        ans.dl=ans.dr=y.c;
        return ans;
    }
    ans.l+=(y.s+(l-1)*y.c);
    ans.r+=(y.s+(r-1)*y.c);
    ans.dl+=y.c;
    ans.dr+=y.c;
    return ans;
}

ll n,q;
ll a[300010];
play seg[1200040];
dev lz[1200040];
bool marked[1200040],bottom[1200040];

void build(ll v,ll st,ll ed)
{
    if(st==ed)
    {
        seg[v]={a[st],a[st],1,1,0,1,0,1};
        bottom[v]=true;
        return;
    }
    ll mid=(st+ed)>>1;
    build(2*v,st,mid);
    build(2*v+1,mid+1,ed);
    seg[v]=mix(seg[2*v],seg[2*v+1]);
}

void push_down(ll v,ll l,ll r)
{
    if(!marked[v] || bottom[v]) return;
    marked[v]=false;
    marked[2*v]=marked[2*v+1]=true;
    seg[2*v]=mod(seg[2*v],lz[v],l,r);
    lz[2*v]=rep(lz[2*v],lz[v]);
    seg[2*v+1]=mod(seg[2*v+1],lz[v],l,r);
    lz[2*v+1]=rep(lz[2*v+1],lz[v]);
    lz[v]={false,0,0};
}

void upd(ll v,ll st,ll ed,ll l,ll r,dev x)
{
    if(st>ed) return;
    if(st==l && ed==r)
    {
        marked[v]=true;
        seg[v]=mod(seg[v],x,l,r);
        lz[v]=rep(lz[v],x);
        return;
    }
    push_down(v,l,r);
    ll mid=(l+r)>>1;
    upd(2*v,st,min(mid,ed),l,mid,x);
    upd(2*v+1,max(mid+1,st),ed,mid+1,r,x);
    seg[v]=mix(seg[2*v],seg[2*v+1]);
}

play que(ll v,ll st,ll ed,ll l,ll r)
{
    if(l==st && r==ed) return seg[v];
    push_down(v,l,r);
    ll mid=(l+r)>>1;
    if(ed<=mid) return que(2*v,st,ed,l,mid);
    if(st>mid) return que(2*v+1,st,ed,mid+1,r);
    return mix(que(2*v,st,mid,l,mid),que(2*v+1,mid+1,ed,mid+1,r));
}

int main()
{
    scanf("%lld %lld",&n,&q);
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(ll i=0;i<1200040;i++)
    {
        marked[i]=false;
        bottom[i]=false;
        lz[i]={false,0,0};
    }
    build(1,1,n);
    ll ty,l,r;
    ll s,c;
    dev temp;
    while(q--)
    {
        scanf("%lld",&ty);
        if(ty==1)
        {
            scanf("%lld %lld %lld %lld",&l,&r,&s,&c);
            temp={false,s+(1-l)*c,c};
            upd(1,l,r,1,n,temp);
        }
        else if(ty==2)
        {
            scanf("%lld %lld %lld %lld",&l,&r,&s,&c);
            temp={true,s+(1-l)*c,c};
            upd(1,l,r,1,n,temp);
        }
        else
        {
            scanf("%lld %lld",&l,&r);
            printf("%lld\n",(que(1,l,r,1,n)).c);
        }
    }
}

Compilation message (stderr)

Progression.cpp: In function 'int main()':
Progression.cpp:183:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |     scanf("%lld %lld",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Progression.cpp:184:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |     for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
      |                          ~~~~~^~~~~~~~~~~~~~
Progression.cpp:197:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  197 |         scanf("%lld",&ty);
      |         ~~~~~^~~~~~~~~~~~
Progression.cpp:200:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 |             scanf("%lld %lld %lld %lld",&l,&r,&s,&c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:206:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  206 |             scanf("%lld %lld %lld %lld",&l,&r,&s,&c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:212:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |             scanf("%lld %lld",&l,&r);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 0 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 0 / 13
• Subtask 6: 0 / 17