Submission #1124276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124276		imarn	Fire (JOI20_ho_t5)	C++20	100 / 100	366 ms	57088 KiB

ho_t5

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int inf=1e9+7,k = 2e5+5;
const int mxn=5e5+5;
struct fen{
    ll fw[mxn];
    void add(int i,ll amt){i+=k;
        for(;i<mxn;i+=i&-i)fw[i]+=amt;
    }
    ll qr(int i,ll rs=0){i+=k;
        for(;i;i-=i&-i)rs+=fw[i];
        return rs;
    }
}fw[20];
ll a[mxn],l[mxn],r[mxn],sm=0,rs[mxn]{0};
vector<pii>g[mxn],qr[mxn];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    stack<int>st;
    for(int i=1;i<=n;i++){
        while(!st.empty()&&a[st.top()]<a[i])st.pop();
        if(!st.empty())l[i]=st.top();st.push(i);
    }while(!st.empty())st.pop();
    for(int i=n;i>=1;i--){
        while(!st.empty()&&a[st.top()]<=a[i])st.pop();
        if(!st.empty())r[i]=st.top();
        else r[i]=n+1;
        st.push(i);
    }
    for(int i=1;i<=q;i++){
        int l,r,t;cin>>t>>l>>r;
        qr[l-1].pb({-i,t});
        qr[r].pb({i,t});
    }
    for(int i=1;i<=n;i++)g[i].pb({1,i}),g[r[i]].pb({2,i});
    for(int j=1;j<=n;j++){
        sm+=a[j];
        for(auto [u,i] : g[j]){
            if(u==1){
                //if(i!=3)continue;
                fw[0].add(-i,-a[i]);
                fw[1].add(-i,a[i]);
                fw[2].add(-i,-i*a[i]);
                if(l[i]!=0)fw[3].add(i-l[i],(i-l[i])*a[i]);
                if(l[i]!=0)fw[4].add(i-l[i],-a[i]);
                if(l[i]!=0)fw[5].add(-l[i],a[i]);
                if(l[i]!=0)fw[6].add(-l[i],l[i]*a[i]);
            }
            if(u==2){
                //if(i!=3)continue;
                fw[0].add(-i,a[i]);
                fw[1].add(-i,-a[i]);
                fw[2].add(-i,i*a[i]);
                if(l[i]!=0)fw[5].add(-l[i],-a[i]);
                if(l[i]!=0)fw[6].add(-l[i],-l[i]*a[i]);
                fw[7].add(r[i]-i,-a[i]);
                fw[8].add(r[i]-i,r[i]*a[i]);
                fw[9].add(r[i]-i,-i*a[i]);
                if(l[i]!=0)fw[10].add(r[i]-l[i],-r[i]*a[i]);
                if(l[i]!=0)fw[11].add(r[i]-l[i],l[i]*a[i]);
                if(l[i]!=0)fw[12].add(r[i]-l[i],a[i]);
            }
        }
        for(auto [i,t] : qr[j]){
            ll x = (i<0?-1:1);
            i=abs(i);
            if(j!=0)rs[i]+=sm*(t+1)+(t+1)*fw[0].qr(t-j)+(j+1)*fw[1].qr(t-j)+fw[2].qr(t-j);//(t+1)x or (j+1-i)x for non r[i]
            if(j!=0)rs[i]+=fw[3].qr(t)+(t+1)*fw[4].qr(t);//(j-l[i]-t)x or (i-l[i])x
            if(j!=0)rs[i]+=(t-j)*fw[5].qr(t-j)+fw[6].qr(t-j);// (j-l[i]-t)x=>0 for non r[i]
            if(j!=0)rs[i]+=(t+1)*fw[7].qr(t)+fw[8].qr(t)+fw[9].qr(t);
            if(j!=0)rs[i]+=fw[10].qr(t)+fw[11].qr(t)+(t+1)*fw[12].qr(t);
            rs[i]*=x;
        }
    }for(int i=1;i<=q;i++)cout<<rs[i]<<'\n';
}

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80