Submission #682638

#	Time	Username	Problem	Language	Result	Execution time	Memory
682638		jk410	Fire (JOI20_ho_t5)	C++17	100 / 100	776 ms	54600 KiB

ho_t5

#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
struct line{
    ll a,b;
    ll get_val(ll x){
        return a*x+b;
    }
};
line operator+(const line &l1,const line &l2){
    return {l1.a+l2.a,l1.b+l2.b};
}
line operator*(const line &l,const ll k){
    return {l.a*k,l.b*k};
}
struct us{
    int t,x;
    line l;
    bool operator<(const us &tmp){
        if (t!=tmp.t)
            return t<tmp.t;
        return l.a>tmp.l.a;
    }
};
struct qs{
    int t,l,r,x;
    bool operator<(const qs &tmp){
        return t<tmp.t;
    }
};
struct node{
    line sum,cnt;
};
node operator+(const node &a,const node &b){
    return {a.sum+b.sum,a.cnt+b.cnt};
}
const ll MAX=1e9+1;
int N,Q;
ll A[200002];
int D1[200001],D2[200001];
node Tree[1<<19];
node update(int x,line v,int l,int r,int n){
    if (x<l||r<x)
        return Tree[n];
    if (l==r)
        return Tree[n]={v*A[x],v};
    int m=(l+r)>>1;
    return Tree[n]=update(x,v,l,m,n<<1)+update(x,v,m+1,r,n<<1|1);
}
ll query(int x,int t,int l,int r,int n){
    if (l==r)
        return A[l]*x;
    int m=(l+r)>>1;
    if (x>Tree[n<<1].cnt.get_val(t))
        return Tree[n<<1].sum.get_val(t)+query(x-Tree[n<<1].cnt.get_val(t),t,m+1,r,n<<1|1);
    return query(x,t,l,m,n<<1);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>Q;
    for (int i=1; i<=N; i++)
        cin>>A[i];
    A[N+1]=MAX;
    stack<int> s;
    for (int i=1; i<=N; i++){
        while (!s.empty()&&A[s.top()]<A[i])
            s.pop();
        if (!s.empty())
            D1[i]=s.top();
        s.push(i);
    }
    while (!s.empty())
        s.pop();
    s.push(N+1);
    for (int i=N; i; i--){
        while (A[s.top()]<=A[i])
            s.pop();
        D2[i]=s.top();
        s.push(i);
    }
    vector<us> vu;
    for (int i=1; i<=N; i++){
        if (D1[i]){
            int t1=i-D1[i]-1,t2=D2[i]-i-1;
            if (t1>t2)
                swap(t1,t2);
            vu.push_back({0,i,{1,1}});
            vu.push_back({t1,i,{0,t1+1}});
            vu.push_back({t2,i,{-1,t1+t2+1}});
            vu.push_back({t1+t2+1,i,{0,0}});
        }
        else{
            int t=D2[i]-i-1;
            vu.push_back({0,i,{1,1}});
            vu.push_back({t,i,{0,t+1}});
        }
    }
    sort(all(vu));
    vector<qs> vq;
    for (int i=0,t,l,r; i<Q; i++){
        cin>>t>>l>>r;
        vq.push_back({t,l,r,i});
    }
    sort(all(vq));
    vector<ll> ans(Q);
    for (int t=0,iu=0,iq=0; t<=N; t++){
        for (; iu<(int)vu.size()&&vu[iu].t==t; iu++)
            update(vu[iu].x,vu[iu].l,1,N,1);
        for (; iq<(int)vq.size()&&vq[iq].t==t; iq++)
            ans[vq[iq].x]=query(vq[iq].r,t,1,N,1)-query(vq[iq].l-1,t,1,N,1);
    }
    for (int i=0; i<Q; i++)
        cout<<ans[i]<<"\n";
    return 0;
}

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