Submission #1039420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039420		Trent	Fish 3 (JOI24_fish3)	C++17	100 / 100	612 ms	52820 KiB

Main

#include "bits/stdc++.h"

using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
typedef long long ll;
struct pii{int a, b;};
const int MN = 3e5 + 10, MQ = 3e5 + 10;
struct query{int l, r, i;};
ll c[MN];
ll ans[MQ];
vector<query> byR[MN];
ll ti[MN], buf[MN];
bool pos[MN];
struct invl{int l, r; ll ti;};

struct node{ll su, lz;};
const int ME = 4 * MN;
node seg[ME];
void push(int v, int nl, int nr){
	if(2*v+1 < ME){
		int mid = (nl+nr)/2;
		seg[2*v].su += (ll) (mid-nl+1) * seg[v].lz;
		seg[2*v+1].su += (ll) (nr-mid) * seg[v].lz;
		seg[2*v].lz += seg[v].lz;
		seg[2*v+1].lz += seg[v].lz;
		seg[v].lz = 0;
	}
}
void upd(int v, int nl, int nr, int l, int r, ll by) {
	push(v, nl, nr);
	if(l > r) return;
	if(nl == l && nr == r) {
		seg[v].su += (ll) (nr-nl+1) * by;
		seg[v].lz += by;
	} else {
		int mid = (nl+nr)/2;
		upd(2*v, nl, mid, l, min(mid, r), by);
		upd(2*v+1, mid+1, nr, max(mid+1, l), r, by);
		seg[v].su = seg[2*v].su + seg[2*v+1].su;
	}
}
ll qu(int v, int nl, int nr, int l, int r){
	push(v, nl, nr);
	if(l > r) return 0;
	else if(nl == l && nr == r) return seg[v].su;
	else {
		int mid = (nl+nr)/2;
		return qu(2*v,nl,mid,l,min(mid,r)) + qu(2*v+1,mid+1,nr,max(mid+1,l),r);
	}
}

ll ceilDiv(ll a, ll b){
	return (a-1)/b+1;
}
int main() {
	int n;
	ll d; cin >> n >> d;
	REP(i, 1, n+1) {
		pos[i] = true;
	}
	REP(i, 1, n+1) cin >> c[i];
	int q; cin >> q;
	forR(i, q){
		query cur={}; cin >> cur.l >> cur.r;
		cur.i = i;
		byR[cur.r].push_back(cur);
	}
	vector<invl> ivs;
	REP(i, 1, n+1){
		if(i == 1 || c[i] >= c[i-1] - d*ti[i-1]) {
			if(!ivs.empty()) ivs.back().ti = (c[i] - (c[i-1]-d*ti[i-1])) / d;
			ivs.push_back({i, i, 83742});
		} else {
			ll ct = ceilDiv((c[i-1]-d*ti[i-1]) - c[i], d);
			while(ct > 0){
				if(ivs.size() == 1){
					upd(1,1,n,ivs.back().l,ivs.back().r,ct);
					ct = 0;
				} else {
					invl& sLast = ivs[(int) ivs.size() - 2];
					if(sLast.ti > ct) {
						upd(1,1,n,ivs.back().l,ivs.back().r,ct);
						sLast.ti -= ct;
						ct = 0;
					} else {
						upd(1,1,n,ivs.back().l,ivs.back().r,sLast.ti);
						ct -= sLast.ti;
						sLast.r = ivs.back().r;
						sLast.ti = 283742;
						ivs.pop_back();
					}
				}
			}
			ivs.back().r = i;
		}
		for(auto [l, r, ind] : byR[i]){
			if(c[l] - d * qu(1,1,n,l,l) < 0) ans[ind] = -1;
			else {
				ans[ind] = qu(1,1,n,l,i);
			}
		}
	}
	forR(i, q) cout << ans[i] << '\n';
}

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