제출 #1139309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139309		ByeWorld	Fish 3 (JOI24_fish3)	C++20	9 / 100	2095 ms	14712 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+50;
const int SQRT = 610;
const int MAXA = 50;
const int MOD = 998244353;
const int LOG = 21;
const int INF = 1e16+100;
const int INF2 = 1e18;
const ld EPS = 1e-12;

int n, d, c[MAXN], ans[MAXN], val[MAXN], su[MAXN];
vector <pii> que[MAXN];

struct seg {
    int st[4*MAXN], laz[4*MAXN];
    void bd(int id, int l, int r){
        laz[id] = -1;
        if(l==r) return;
        bd(lf,l,md); bd(rg,md+1,r);
    }
    void bnc(int id, int l, int r){
        if(laz[id]==-1) return;
        laz[lf] = laz[id]; st[lf] = (md-l+1) * laz[id];
        laz[rg] = laz[id]; st[rg] = (r-md) * laz[id];
        laz[id] = -1;
    }
    int que(int id, int l, int r, int x, int y){
        if(x<=l && r<=y) return st[id];
        if(r<x || y<l) return 0;
        bnc(id,l,r);
        return que(lf,l,md,x,y) + que(rg,md+1,r,x,y);
    }
    int upd(int id, int l, int r, int x, int y, int p){
        if(x<=l && r<=y){
            laz[id] = p;
            return st[id] = (r-l+1) * p;
        }
        if(r<x || y<l) return st[id];
        bnc(id,l,r);
        return st[id] = upd(lf,l,md,x,y,p) + upd(rg,md+1,r,x,y,p);
    }
} A;
signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>d;
    for(int i=1; i<=n; i++){
        cin >> c[i];
    }
    // for(int i=n-1; i>=1; i--){
    //     val[i] = val[i+1] + (c[i]-c[i+1]+d-1)/d;
    //     su[i] = su[i+1] + val[i];
    //     // cout << i << ' ' << val[i] << ' ' << su[i] << " pp\n";
    // }
    int q; cin>>q;
    for(int i=1; i<=q; i++){
        int l, r; cin>>l>>r;
        if(l==r){ ans[i] = 0; continue; }
        r--;
        int nw = 0; bool can = 1;
        for(int j=r; j>=l; j--){
            if(c[j] >= c[j+1]) nw += (c[j]-c[j+1]+d-1)/d;
            else nw -= (c[j+1]-c[j])/d;
            if(nw*d > c[j]) can = 0;
            nw = max(0ll, nw);
            ans[i] += nw;
        }
        if(!can) ans[i] = -1;
        // if((val[l]-val[r+1])*d > c[l]){ ans[i] = -1; continue; }

        // ans[i] = su[l]-su[r+1] - (r-l+1) * val[r+1];
        // cout << su[l]-su[r+1] << " su\n";
    }
    for(int i=1; i<=q;i++) cout << ans[i] << " \n";
}

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