Submission #1284807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284807		Muhammad_Aneeq	Fish 3 (JOI24_fish3)	C++20	28 / 100	571 ms	49944 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
int const N=3e5+10;
int c[N]={};
int ans[N]={};
vector<pair<int,int>>ind[N];
struct node
{
    int sm=0,vl=0,lazy=0;
};
node seg[4*N]={};
void push(int i,int st,int en)
{
    int mid=(st+en)/2;
    int s[2]={};
    s[0]=mid-st+1;
    s[1]=en-mid;
    for (int j=2*i;j<=2*i+1;j++)
    {
        seg[j].vl=seg[j].sm-s[j-2*i]*seg[i].lazy;
        seg[j].lazy=seg[i].lazy;
    }
    seg[i].lazy=-1;
}
void build(int i,int st,int en)
{
    seg[i].lazy=-1;
    if (st==en)
    {
        seg[i].sm=c[st];
        return;
    }
    int mid=(st+en)/2;
    build(i*2,st,mid);
    build(i*2+1,mid+1,en);
    seg[i].sm=seg[i*2].sm+seg[i*2+1].sm;
}
void update(int i,int st,int en,int l,int r,int val)
{
    if (st>=l&&en<=r)
    {
        seg[i].vl=seg[i].sm-(en-st+1)*val;
        seg[i].lazy=val;
        return;
    }
    if (st>r||en<l)
        return;
    if (seg[i].lazy!=-1)
        push(i,st,en);
    int mid=(st+en)/2;
    update(i*2,st,mid,l,r,val);update(i*2+1,mid+1,en,l,r,val);
    seg[i].vl=seg[i*2].vl+seg[i*2+1].vl;
}
int get(int i,int st,int en,int l,int r)
{
    if (st>=l&&en<=r)
        return seg[i].vl;
    if (st>r||en<l)
        return 0;
    if (seg[i].lazy!=-1)
        push(i,st,en);
    int mid=(st+en)/2;
    return get(i*2,st,mid,l,r)+get(i*2+1,mid+1,en,l,r);
}
inline void solve()
{
    int n,D;
    cin>>n>>D;
    c[0]=-1;
    for (int i=1;i<=n;i++)
        cin>>c[i];
    build(1,1,n);
    int q;
    cin>>q;
    for (int i=0;i<q;i++)
    {
        int l,r;
        cin>>l>>r;
        ind[r].push_back({l,i});
    }
    vector<int>z={0};
    for (int i=1;i<=n;i++)
    {
        while (z.size()&&c[z.back()]>c[i])
            z.pop_back();
        update(1,1,n,z.back()+1,i,c[i]);
        z.push_back(i);
        for (auto [l,inx]:ind[i])
            ans[inx]=get(1,1,n,l,i);
    }
    for (int i=0;i<q;i++)
        cout<<ans[i]<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

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