Submission #1120059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120059		Math4Life2020	Ski 2 (JOI24_ski2)	C++17	0 / 100	6 ms	852 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; const ll INF = 2e18;
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 v2(ll x) {
	return (__builtin_ctz(x));
}

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

ll st[2*Nm];

void upd(ll x, ll v) { //sets value at x to v
	st[x+Nm]=v;
	ll p = (x+Nm);
	do {
		p=p/2;
		st[p]=st[2*p]+st[2*p+1];
	} while (p>1);
}

ll qst(ll a, ll b) {
	if (a>b) {
		return 0;
	}
	ll va = v2(a); ll vb = v2(b+1);
	if (va>=vb) {
		return (st[(a>>va)+(1LL<<(E-va))]+qst(a+(1LL<<va),b));
	} else {
		return (st[(b>>vb)+(1LL<<(E-vb))]+qst(a,b-(1LL<<vb)));
	}
}

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--;
		ans[q]=-2;
		qr[r].push_back({l,q});
	}
	vector<pii> cnums; //{x-coord,value}
	cnums.push_back({-1,-INF});
	//in strictly INCREASING order
	for (ll r=0;r<N;r++) {
		//cout << "process r="<<r<<"\n";
		while (!cnums.empty()) {
			ll vb = cnums.back().second;
			if (vb>=b[r]) {
				ll xbt = cnums.back().first;
				upd(xbt,0);
				cnums.pop_back();
			} else {
				break;
			}
		}
		assert(!cnums.empty());
		ll xprev = cnums.back().first;
		upd(r,b[r]*(r-xprev));
		cnums.push_back({r,b[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);
			// }
			pii pnext = *lower_bound(cnums.begin(),cnums.end(),(pii){l,-INF});
			ll l1 = pnext.first; ll nbv = pnext.second;
			vf -= (l1-l+1)*nbv;
			for (ll i=l;i<=l1;i++) {
				assert(rmq(i,r)==nbv);
			}
			vf -= qst(l1+1,r);
			ans[q]=vf;
		}
		for (pii p0: cnums) {
			//cout << "p0 in cnums: "<<p0.first<<","<<p0.second<<"\n";
		}
	}
	for (ll q=0;q<Q;q++) {
		//assert(ans[q]!=-2);
		cout << ans[q]<<"\n";
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:127:12: warning: variable 'p0' set but not used [-Wunused-but-set-variable]
  127 |   for (pii p0: cnums) {
      |            ^~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 33
• Subtask 5: 0 / 27
• Subtask 6: 0 / 14