Submission #1103735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103735		vjudge1	Fish 3 (JOI24_fish3)	C++17	100 / 100	584 ms	64704 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define all(x) x.begin(),x.end()
#define int long long

typedef long long ll;
typedef pair<int,int> pii;
typedef double db;

const ll maxn=3e5+69;
const ll offset=2e5;
const ll inf=1e18;
const int base=350;
const ll mod=1e9+7;

int n,d;
int st[maxn*4],lazy[maxn*4];
vector<pii> qr[maxn];
int a[maxn],b[maxn],c[maxn],pre[maxn],x[maxn],ans[maxn];
void push_down(int id,int l,int r)
{
    int mid=l+r>>1;
    int& v=lazy[id];
    st[id*2]+= v*(mid-l+1);
    lazy[id*2]+=v;
    st[id*2+1]+=v*(r-mid);
    lazy[id*2+1]+=v;
    v=0;
}
void Update(int u,int v,int val,int id=1,int l=1,int r=n)
{
    if (u>r || v<l) return;
    if (u<=l && r<=v)
    {
        st[id]+=val*(r-l+1);
        lazy[id]+=val;
        return;
    }
    int mid=l+r>>1;
    if (lazy[id]!=0) push_down(id,l,r);
    Update(u,v,val,id*2,l,mid);
    Update(u,v,val,id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
}
int Get(int u,int v,int id=1,int l=1,int r=n)
{
    if (u>r || v<l) return 0;
    if (u<=l && r<=v) return st[id];
    int mid=l+r>>1;
    if (lazy[id]!=0) push_down(id,l,r);
    return Get(u,v,id*2,l,mid)+ Get(u,v,id*2+1,mid+1,r);
}
void sol()
{
    cin >> n>>d;
    for1(i,1,n) cin >> a[i];
    for1(i,1,n)
    {
        b[i]=a[i]%d;
        c[i]=a[i]/d;
        pre[i]=pre[i-1]+c[i];
        x[i]=x[i-1]+(b[i]<b[i-1]);
    }
    int q; cin >>q;
    for1(i,1,q)
    {
        int l,r; cin >> l>>r;
        qr[r].pb({l,i});
    }
    vector<pii> L;
    L.pb({-inf,0});
    for1(i,1,n)
    {
        Update(i,i,c[i]);
//        cerr<<"cccdc "<<i<<' '<<c[i]<<'\n';
        while (L.back().fi>=c[i]-x[i])
        {
            int j=L.back().se;
            int cj=L.back().fi;
//            cerr<< j<<'\n';
            L.pop_back();
            Update(L.back().se+1,j,c[i]-x[i]-cj);
//            cerr<< L.back().se+1<<' '<<j<<' '<<c[i]-x[i]-cj<<'\n';
        }
        L.pb({c[i]-x[i],i});
        for(auto [l,j]:qr[i])
        {
//            cerr<< Get(l,l)<<'\n';
            if (Get(l,l)<0) {ans[j]=-1; continue;}
            ans[j]=pre[i]-pre[l-1]-Get(l,i);
        }
    }
    for1(i,1,q) cout << ans[i]<<'\n';

}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("990G.inp","r",stdin);
//    freopen("990G.out","w",stdout);

    int t=1;//cin >> t;
    for1(i,1,t) {
//        cout << "Case #"<<i<<": ";
        sol();
    }
}

/*
5 1
3 1 4 1 5
1
2 4



*/

Compilation message (stderr)

Main.cpp: In function 'void push_down(long long int, long long int, long long int)':
Main.cpp:29:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid=l+r>>1;
      |             ~^~
Main.cpp: In function 'void Update(long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:46:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mid=l+r>>1;
      |             ~^~
Main.cpp: In function 'long long int Get(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:56:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |     int mid=l+r>>1;
      |             ~^~

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