Submission #1120048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120048		Math4Life2020	Fish 3 (JOI24_fish3)	C++17	9 / 100	2066 ms	83336 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 524288; const ll E = 19;
ll rmqv[Nm][E+1];

void initRMQ(vector<ll> b) {
	ll N = b.size();
	for (ll i=0;i<N;i++) {
		rmqv[i][0]=b[i];
	}
	for (ll j=1;j<=E;j++) {
		for (ll i=0;i<(N-(1LL<<j)+1);i++) {
			rmqv[i][j]=min(rmqv[i][j-1],rmqv[i+(1LL<<(j-1))][j-1]);
		}
	}
}

ll l2(ll x) {
	return (31-__builtin_clz(x));
}

ll rmq(ll a, ll b) {
	ll l = l2(b-a+1);
	return min(rmqv[a][l],rmqv[b-(1LL<<l)+1][l]);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll N,D; cin >> N >> D;
	ll c[N]; ll rem[N]; ll d0[N]; ll a[N]; vector<ll> b;
	for (ll i=0;i<N;i++) {
		cin >> c[i];
		rem[i]=c[i]%D;
		d0[i]=c[i]/D;
	}
	a[0]=0;
	b.push_back(d0[0]);
	for (ll i=1;i<N;i++) {
		if (rem[i-1]>rem[i]) {
			a[i]=a[i-1]+1;
		} else {
			a[i]=a[i-1];
		}
		b.push_back(d0[i]-a[i]);
	}
	ll psb[N+1];
	psb[0]=0;
	for (ll i=0;i<N;i++) {
		psb[i+1]=psb[i]+b[i];
	}
	initRMQ(b);
	ll Q; cin >> Q;
	ll ans[Q];
	vector<pii> qr[N]; //qr[right]={left,qryIndex}
	for (ll q=0;q<Q;q++) {
		ll l,r; cin >> l >> r;
		l--; r--;
		qr[r].push_back({l,q});
	}
	vector<pii> cnums; //{value,x-coord}
	//in strictly INCREASING order
	for (ll r=0;r<N;r++) {
		while (!cnums.empty()) {
			ll vb = cnums.back().first;
			if (vb>=b[r]) {
				cnums.pop_back();
			} else {
				break;
			}
		}
		cnums.push_back({b[r],r});
		for (pii qrn: qr[r]) {
			ll l = qrn.first; ll q = qrn.second;
			if (rmq(l,r)<(-a[l])) {
				ans[q]=-1; continue;
			}
			ll vf = psb[r+1]-psb[l];
			for (ll i=l;i<=r;i++) {
				vf -= rmq(i,r);
			}
			ans[q]=vf;
		}
	}
	for (ll q=0;q<Q;q++) {
		cout << ans[q]<<"\n";
	}
}

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