Submission #1039417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039417		Trent	Fish 3 (JOI24_fish3)	C++17	9 / 100	2076 ms	21708 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;};

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){
					for(int j = ivs.back().l; j <= ivs.back().r; ++j) ti[j] += ct;
					ct = 0;
				} else {
					invl& sLast = ivs[(int) ivs.size() - 2];
					if(sLast.ti > ct) {
						for(int j = ivs.back().l; j <= ivs.back().r; ++j) ti[j] += ct;
						sLast.ti -= ct;
						ct = 0;
					} else {
						for(int j = ivs.back().l; j <= ivs.back().r; ++j) ti[j] += 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*ti[l] < 0) ans[ind] = -1;
			else {
				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