Submission #682523

#	Time	Username	Problem	Language	Result	Execution time	Memory
682523		jk410	Fire (JOI20_ho_t5)	C++17	0 / 100	1079 ms	40812 KiB

ho_t5

#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
struct node{
    ll sum,dsum;
    int cnt,dcnt;
    int t;
    pair<ll,int> get_val(int ct){
        return {sum+dsum*(ct-t),cnt+dcnt*(ct-t)};
    }
    void update(ll vs,int vc,int ct){
        auto tmp=get_val(ct);
        sum=tmp.first;
        dsum+=vs;
        cnt=tmp.second;
        dcnt+=vc;
        t=ct;
    }
};
node operator+(const node &a,const node &b){
    node ret;
    ret.sum=a.sum+b.sum;
    ret.dsum=a.dsum+b.dsum;
    ret.cnt=a.cnt+b.cnt;
    ret.dcnt=a.dcnt+b.dcnt;
    ret.t=max(a.t,b.t);
    return ret;
}
const int MAX=(int)1e9+1;
int N,Q;
int A[200002];
int D1[200001],D2[200001];
node Tree[1<<19];
node init(int l,int r,int n){
    if (l==r)
        return Tree[n]={A[l],A[l],1,1,0};
    int m=(l+r)>>1;
    return Tree[n]=init(l,m,n<<1)+init(m+1,r,n<<1|1);
}
void update(int x,int v,int ct,int l,int r,int n){
    Tree[n].update(A[x]*v,v,ct);
    if (l==r)
        return;
    int m=(l+r)>>1;
    if (x>m)
        update(x,v,ct,m+1,r,n<<1|1);
    else
        update(x,v,ct,l,m,n<<1);
}
pair<ll,int> query(int lx,int rx,int ct,int l,int r,int n){
    if (r<lx||rx<l)
        return {0,0};
    if (lx<=l&&r<=rx)
        return Tree[n].get_val(ct);
    int m=(l+r)>>1;
    auto ret1=query(lx,rx,ct,l,m,n<<1);
    auto ret2=query(lx,rx,ct,m+1,r,n<<1|1);
    return {ret1.first+ret2.first,ret1.second+ret2.second};
}
ll my_query(int x,int ct){
    if (!x)
        return 0;
    int l=1,r=N,k;
    pair<ll,int> ret;
    while (l<=r){
        int m=(l+r)>>1;
        auto tmp=query(1,m,ct,1,N,1);
        if (tmp.second>=x){
            k=m;
            ret=tmp;
            r=m-1;
        }
        else
            l=m+1;
    }
    return ret.first-(ll)A[k]*(ret.second-x);
}
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<pair<int,pair<int,int>>> vu;
    for (int i=1; i<=N; i++){
        if (D1[i]){
            int t1=i-D1[i]-1,t2=D2[i]-i-1;
            vu.push_back({t1,{i,-1}});
            vu.push_back({t2,{i,-1}});
            vu.push_back({t1+t2+1,{i,1}});
        }
        else{
            int t=D2[i]-i-1;
            vu.push_back({t,{i,-1}});
        }
    }
    sort(all(vu));
    vector<pair<int,pair<pair<int,int>,int>>> 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));
    init(1,N,1);
    vector<int> ans(Q);
    for (int t=0,ui=0,qi=0; t<=N; t++){
        for (; qi<(int)vq.size()&&vq[qi].first==t; qi++)
            ans[vq[qi].second.second]=my_query(vq[qi].second.first.second,t)-my_query(vq[qi].second.first.first-1,t);
        for (; ui<(int)vu.size()&&vu[ui].first==t; ui++)
            update(vu[ui].second.first,vu[ui].second.second,t,1,N,1);
    }
    for (int i=0; i<Q; i++)
        cout<<ans[i]<<"\n";
    return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'll my_query(int, int)':
ho_t5.cpp:77:29: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |     return ret.first-(ll)A[k]*(ret.second-x);
      |                          ~~~^

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