Submission #978218

#	Time	Username	Problem	Language	Result	Execution time	Memory
978218		sleepntsheep	Fish 3 (JOI24_fish3)	C++17	28 / 100	444 ms	52364 KiB

Main

long long lo(long long a,long long b){return a<b?a:b;}
#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<vector>
#include<utility>

#define N 300005
int n,q;
long long d,c[N],pc[N],zz[N];
long long tt[N<<2],lz[N<<2];

void push(int v,int l,int r)
{
    if(~lz[v])
    {
        tt[v]=1ll*(r-l+1)*lz[v];
        if(l-r)lz[2*v+1]=lz[2*v+2]=lz[v];
        lz[v]=-1;
    }
}

void upd(int v,int l,int r,int x,int y,long long k)
{
    push(v,l,r);
    if(r<x||y<l)return;
    if(x<=l&&r<=y) { lz[v]=k;push(v,l,r);return; }
    upd(2*v+1,l,(l+r)/2,x,y,k);
    upd(2*v+2,(l+r)/2+1,r,x,y,k);
    tt[v]=tt[2*v+1]+tt[2*v+2];
}

long long qry(int v,int l,int r,int x,int y)
{
    push(v,l,r);
    if(r<x||y<l)return 0;
    if(x<=l&&r<=y)return tt[v];
    return qry(2*v+1,l,l+r>>1,x,y)+qry(2*v+2,(l+r)/2+1,r,x,y);
}

std::vector<std::pair<int, int> > qryo[N];

int stk[N],top,prev_smol[N];

int main()
{
    scanf("%d%lld",&n,&d);
    if(d-1)__builtin_trap();
    memset(lz,-1,sizeof lz);

    for(int i=1;i<=n;++i)
    {
        scanf("%lld",c+i),pc[i]=pc[i-1]+c[i];
    }

    for(int i=n;i>=1;stk[top++]=i--)
        while(top&&c[stk[top-1]]>=c[i])prev_smol[stk[--top]]=i;


    scanf("%d",&q);

    for(int l,r,i=0;i<q;++i)
        scanf("%d%d",&l,&r),
        qryo[r].push_back(std::make_pair(l,i));

    for(int i=1;i<=n;++i)
    {
        upd(0,1,n,prev_smol[i]+1,i,c[i]);
        for(auto[l,I]:qryo[i])
        {
            zz[I]=pc[i]-pc[l-1]-qry(0,1,n,l,i);
        }
    }

    for(int i=0;i<q;++i)printf("%lld\n",zz[i]);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'long long int qry(int, int, int, int, int)':
Main.cpp:39:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     return qry(2*v+1,l,l+r>>1,x,y)+qry(2*v+2,(l+r)/2+1,r,x,y);
      |                        ~^~
Main.cpp: In function 'int main()':
Main.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d%lld",&n,&d);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%lld",c+i),pc[i]=pc[i-1]+c[i];
      |         ~~~~~^~~~~~~~~~~~
Main.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
Main.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf("%d%d",&l,&r),
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 7
• Subtask 3: 28 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36