Submission #1202941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202941		walizamanee	Fish 3 (JOI24_fish3)	C++20	100 / 100	318 ms	26996 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n , q , one , two , uno , aage , stcksiz;
long long d , c[300001] , pre[300001] , presum[300001] , tot[300001] , vag[300001] , ans[300001] , ek , dui , tin;
long long stckans[300001];


deque<pair<long long , int>> stck; // f9irst val second index
struct QQ{
    int first;
    int second;
    long long third;
};
bool comp( QQ me , QQ him ) {
    return me.first < him.first;
}
vector<QQ> qq;
int getans( int me ) {
    int l = 1;
    int r = (int)stck.size() - 1;
    while( l < r ) {
        int m = (l + r) / 2;
        if( stck[m].second >= me ) r = m;
        else l = m + 1;
    }
    return l;
}


int main() {
    
    cin >> n >> d;
    for( int z = 1; z <= n; z++ ) {
        cin >> c[z];
        vag[z] = c[z] % d;
        tot[z] = (c[z] - (c[z] % d)) / d;
        tot[z] = tot[z] + tot[z - 1];
        if( vag[z] < vag[z - 1] ) pre[z] = 1;
        pre[z] += pre[z - 1]; // pre is the count before this
        presum[z] = pre[z] + presum[z - 1];
    }
    cin >> q;
    for( int z = 1; z <= q; z++ ) {
        cin >> one >> two;
        qq.push_back({two , one , z });
    }
    qq.push_back({0 , 0 , 0});
    sort(qq.begin() , qq.end() , comp );
    stck.push_back({(ll)(-2000000000000 ) , 0 });
   
    for( int z = 1; z <= q; z++ ) {
        if( qq[z].first > qq[z - 1].first  ) {
            for( int y = qq[z - 1].first + 1; y <= qq[z].first; y++ ) {
                ek = ( tot[y] - tot[y - 1] ) - pre[y];
                stcksiz = (int)stck.size();
                while( stcksiz > 1 && stck.back().first >= ek  ) {
                    stck.pop_back();
                    stcksiz--;
                    stckans[stcksiz] = 0;
                }
                one = stck.back().second;
                tin = stck.back().first;
                stck.push_back({ek , y});
                stckans[stcksiz] = (ll)(y - one)*(ek); // was ek - tin
                stckans[stcksiz] += stckans[stcksiz - 1];
            }
        }
        one = qq[z].second;
        two = getans(one);
        tin = stckans[(int)stck.size() - 1] - stckans[two];
        tin += stck[two].first * ( (ll)(stck[two].second - one + 1)  );
        //cout << tin << "\n";
        dui = stck[two].first + pre[one]; // kotote thakar kotha
        if( dui < 0 ) ans[qq[z].third] = -1;
        else{
           // cout << dui << "\n";
            tin += ((dui - stck[two].first)  * (ll)(qq[z].first - qq[z].second + 1));
            //cout << tin << "\n";
            tin += ( presum[qq[z].first] - presum[qq[z].second] ) - 
            (pre[qq[z].second] * (ll)(qq[z].first - qq[z].second) );
           // cout << tin << "\n";
            tin = (tot[qq[z].first] - tot[qq[z].second - 1]) - tin;
            ans[qq[z].third] = tin;
        
        }
    }
   // for( int z = 0; z < (int)stck.size(); z++ ) {
        //cout << stck[z].first << " " << stck[z].second << " " << stckans[z] << "\n";  
   // }
    for( int z = 1; z <= q; z++ ) cout << ans[z] << "\n";
    return 0;
}

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