Submission #1154709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154709		jiahng	Fish 3 (JOI24_fish3)	C++20	100 / 100	232 ms	37124 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef pair<ll,ll> pill;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF (ll)1e18
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
typedef pair <pi,pi> pipi;
#define maxn 500010

int N,D,Q,A[maxn],ans[maxn];
vpi queries[maxn];

int fw[2][maxn];

int query(int p,int t){
	int ans = 0;
	for (int i=p;i>0;i-=i&(-i)){
		ans += fw[t][i];
	}
	return ans;
}
void update(int p,int v,int t){
	for (int i=p;i<=N;i+=i&(-i)) fw[t][i] += v;
}
void upd(int a,int b,int c){
	//~ cout << "UPD: " << a << ' ' << b << ' ' << c << '\n';
	update(a,c*(1-a),0); update(b+1,c*b,0);
	update(a,c,1); update(b+1,-c,1);
}
int qry(int a,int b){
	int ass = query(a-1,0) + query(a-1,1) * (a-1);
	int bss = query(b,0) + query(b,1)*b;
	
	//~ cout << "QRY: " << a << ' ' << b << ' ' << bss-ass << '\n';
	return bss - ass;
}
int32_t main(){
	fast;
	cin >> N >> D;
	FOR(i,1,N) cin >> A[i];
	cin >> Q;
	int l,r;
	FOR(i,1,Q){
		cin >> l >> r;
		queries[r].pb(pi(l,i));
	}
	
	stack <pipi> st;
	int imp = 1;
	FOR(r,1,N){
		if (st.empty() || st.top().s.s <= A[r]) st.push(pipi(pi(r,r),pi(A[r],A[r])));
		else{
			int l = r, vl = A[r];
			while (!st.empty() && st.top().s.s > vl){
				int amt = (st.top().s.s - vl + D - 1) / D;
				upd(st.top().f.f, st.top().f.s, amt);
				l = st.top().f.f; vl = st.top().s.f - amt * D;
				st.pop();
			}
			st.push(pipi(pi(l,r), pi(vl, A[r])));
		}
		while (imp <= N && A[imp] - D * qry(imp,imp) < 0) imp++;
		aFOR(q, queries[r]){
			ans[q.s] = (q.f < imp ? -1 : qry(q.f,r));
		}
	}
	FOR(i,1,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