Submission #1039394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039394		Trent	Fish 3 (JOI24_fish3)	C++17	9 / 100	2072 ms	29012 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];
bool pos[MN];

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);
	}
	REP(i, 1, n+1){
		for(int j = i-1; j > 0; --j) {
			if(!pos[j+1]) pos[j] = false;
			else if(c[j]-d*ti[j] > c[j+1]-d*ti[j+1]){
				ll needed = ceilDiv(c[j]-d*ti[j]-(c[j+1]-d*ti[j+1]), d);
				ti[j] += needed;
				if(c[j]-ti[j] * d < 0) pos[j] = false;
			}
		}
		for(auto [l, r, ind] : byR[i]){
			for(int j = l; j <= i; ++j) if(!pos[j]) ans[ind] = -1;
			if(ans[ind] != -1){
				for(int j = l; j <= i; ++j){
					ans[ind] += ti[j];
				}
			}				
		}
	}
	forR(i, q) cout << ans[i] << '\n';
}

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