Submission #1098661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098661		flyingkite	Fish 3 (JOI24_fish3)	C++17	100 / 100	760 ms	51796 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll blocks = 350;
ll n,d,q;
ll a[N], res[N];
vector<pll>t[N];
struct segment_tree{
    ll n;
    vector<ll>st, lz;
    void init(ll _n){
        n = _n;
        st.clear(); st.resize(4 * n + 10, 0);
        lz.clear(); lz.resize(4 * n + 10, 0);
    }
    void down(ll id, ll l, ll r){
        st[id] += lz[id] *  (r - l + 1);
        if(l != r) lz[2 * id] += lz[id], lz[2 * id + 1] += lz[id];
        lz[id] = 0;
    }
    void update(ll id, ll l, ll r, ll left, ll right, ll val){
        down(id, l, r);
        if(l > right || r < left) return;
        if(left <= l && r <= right){
            lz[id] += val;
            down(id, l, r);
            return;
        }
        ll mid = (l + r) / 2;
        update(2 * id, l, mid, left, right, val);
        update(2 * id + 1, mid + 1, r, left, right, val);
        st[id] = (st[2 * id] +  st[2 * id + 1]);
    }
    ll get(ll id, ll l, ll r, ll left, ll right){
        down(id, l, r);
        if(l > right || r < left) return 0;
        if(left <= l && r <= right) return st[id];
        ll mid = (l + r) / 2;
        return get(2 * id, l, mid, left, right) + get(2 * id + 1, mid + 1, r, left, right);
    }
    void update(ll l, ll r, ll val){update(1,1,n,l,r,val);}
    ll get(ll l, ll r){return get(1,1,n,l,r);}
} st;
ll get(ll pos){return a[pos] - st.get(pos, pos) * d;}
void to_thic_cau(){
	cin >> n >> d;
	for(int i = 1; i <= n;i++) cin >> a[i];
	cin >> q;
	for(int i = 1; i <= q;i++){
		ll l,r; cin >> l >> r;
		t[r].pb({l, i});
	}
	st.init(n);
	stack<ll>s;
	for(int i = 1; i <= n;i++){
		ll r = i;
		while(s.size()){
			ll l = s.top(), x = get(r - 1), y = get(r);
			if(x <= y) break;
			st.update(l, r - 1, (x - y) / d + ((x - y) % d != 0));
			r = l; s.pop();
		}
		s.push(r);
		for(auto x : t[i]) res[x.S] = (get(x.F) < 0 ? -1 : st.get(x.F, i));
	}
	for(int i = 1; i <= q;i++) cout << res[i] << ' ';
	cout << '\n';
}
 
signed main()   
{ 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

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