Submission #1239309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239309		minhpk	Fish 3 (JOI24_fish3)	C++20	27 / 100	133 ms	46332 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
int z[10000005];
int t[10000005];
vector <pair<int,int>> q[1000005];
int prefix[1000005];
int inf=-1e12;
int res[1000005];
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,d;
    cin >> a >> d;
    for (int i=1;i<=a;i++){
         cin >> z[i];
    }
    int c;
    cin >> c;
    for (int i=1;i<=c;i++){
         int x,y;
         cin >> x >> y;
         q[y].push_back({x,i});
    }

    for (int i=a-1;i>=1;i--){
         if (z[i]>=z[i+1]){
             t[i]=t[i+1]+(z[i]-z[i+1]+d-1)/d;
         }else{
             t[i]=t[i+1]-(z[i+1]-z[i])/d;
         }
    }
    for (int i=1;i<=a;i++){
         prefix[i]=prefix[i-1]+t[i];
    }
    vector <pair<int,int>> st;
    st.push_back({-1*1LL,0LL});
    for (int i=1;i<=a;i++){
         while (st.size()>1 && t[st.back().first]>=t[i]){
               st.pop_back();
         }
         st.push_back({i,st.back().second+(i-st.back().first)*t[i]});
         for (auto p:q[i]){
              int pos=lower_bound(st.begin(),st.end(),make_pair(p.first,inf))-st.begin();
              int pre=st.back().second-st[pos-1].second-t[st[pos].first]*(p.first-1-st[pos-1].first);
              res[p.second]=prefix[i]-prefix[p.first-1]-pre;
              if (z[p.first]<d*(t[p.first]-t[st[pos].first])){
                  res[p.second]=-1;
              }
         }
       //  cerr << i << "\n";
    }
    for (int i=1;i<=c;i++){
         cout << res[i] << "\n";
    }
    return 0;
}

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