Submission #1267639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267639		namhh	Fish 3 (JOI24_fish3)	C++20	100 / 100	506 ms	41748 KiB

Main

//d bt code sai cho nao nen phai chef code:<
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 3e5+5;
int n,q,c[N],d,st[4*N],lazy[4*N],ans[N],pre[N];
vector<pii> rem[N];
struct doan{
	int l,r,vl,vr;
};
vector<doan> emilia;
inline int ceil_div(int x,int y){
    return x / y + !!(x % y);
}
void down(int id, int l, int mid, int r){
	if(lazy[id] != 0){
		st[2*id] += lazy[id] * (mid - l + 1);
		st[2*id+1] += lazy[id] * (r - mid);
		lazy[2*id] += lazy[id];
		lazy[2*id+1] += lazy[id];
		lazy[id] = 0;
	}
}
void update(int id, int l, int r, int u, int v, int val){
	if(l > v || r < u) return;
	if(l >= u && r <= v){
		st[id] += val * (r - l + 1);
		lazy[id] += val;
		return;
	}
	int mid = (l + r) / 2;
	if(l != r) down(id, l, mid, r);
	update(2*id, l, mid, u, v, val);
	update(2*id+1, mid+1, r, u, v, val);
	st[id] = st[2*id] + st[2*id+1];
}
int get(int id, int l, int r, int u, int v){
	if(l > v || r < u) return 0;
	if(l >= u && r <= v) return st[id];
	int mid = (l + r) / 2;
	if(l != r) down(id, l, mid, r);
	return get(2*id, l, mid, u, v) + get(2*id+1, mid+1, r, u, v);
}
inline int valAt(int p){
    return c[p] - get(1,1,n,p,p) * d;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> d;
	for(int i = 1; i <= n; i++){
		cin >> c[i];
	}
	cin >> q;
	for(int i = 1; i <= q; i++){
		int l,r;
		cin >> l >> r;
		rem[r].push_back({l,i});
	}
	stack<int> s;
	for(int i = 1; i <= n; i++){
		int r = i;
		while(!s.empty()){
			int l = s.top();
			int x = valAt(r-1);
			int y = valAt(r);
			if(x <= y) break;
			int need = ceil_div((int)(x - y), (int)d);
			update(1,1,n,l,r-1,need);
			r = l;
			s.pop();
		}
		s.push(r);
		for(auto pr : rem[i]){
			int L = pr.fi, idq = pr.se;
			if(valAt(L) < 0) ans[idq] = -1;
			else ans[idq] = get(1,1,n,L,i);
		}
	}
	for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
//-----+--+----+-==-=*==--=+----------==----------------+=-----==-=+-==----------------
//---===+=----+=----=*=+=*+----------==-----------+=-----==-----==--+-+----------------
//---+=**=-=+---------***+----=------=-------------=-------+-----==-+--=---------------
//----*+-+++**++------=#+----===-----=-------------=-------==-----+-=+=-+--------------
//----++#***+*+++-----=+-----=-=----+---------------+-------+=-----*=-==-+-------------
//---+=+**++**++++==++*=-----===----+---------------+----=---=-----=*+*=-==------------
//---++**==+--++++++***-----+-+-----+---------------==---==--==-----+**---+------------
//----++*#=-+++***+***------+-+-----+----------------=----+---*+=---=*#=-=-+-----------
//-----=**+++*+++**%++-----=--+-----+----------------=----*=--==+==++***-=+==----------
//-------**#**++*%%@==-----=--+-----+-------------=+++++=-+=---+=+=-=+**--+++----------
//---------====+@@%@-=-----+--+--=+++++--------------=----+==--===---+*---+==+---------
//-----------=@*%%%%-=-----+=-==-----=---------------=----+--=-==+-=-=*----++==--------
//----------%#=%=#%%==-----=+--=-----=---------------+----+--===*=*==**=---+-++--------
//--------+@++@=*@%*-=-----=+=-=-----==-------------++-*%%%***=++-+=-+-+---=-===-------
//-------#%-=%=+@%@+-=-----=+=--+++*==*=------------**@*##%*--=-+-----=+---==-+==------
//------=%+-=%=%*@@--=-----=*#*=+*###@%*---------=+*++%***##=-+-+------+---==-=+=------
//-------%*-=%@+@@+-*=-----+-=--@##*##=+==----------=-#*#***-==-+------+---==--++------
//-------+@=+@@*@*-=-=-----=-==-*#%*##=----------------++=+=----+------+---==--==+-----
//--------%@@%%@*=--+=-----=---+=+#==*-------------------==-----+------+---==---=+-----
//----------%+=#-=--==-----+-------===--------------------------*------+---==---+==----
//---------##-%+-=---=-----++----------------------------------=*------=---==---=+=----
//--------=#-*@=-=---=-----**=----------------=----------------+*------=---==----++----
//-------=@==%*-==---=-----++*---------------------------------*+------+---==----++=---
//------=%*-=@--==---=-----+++*-------------------------------**=------+---==----==+---
//------*#--##--==---=-----+++*+--------------------+--------+**=------+---=-----==+---
//-----=@=--@*---=---=-----+++#+*=--------=+=----=+=-------=#+**-------+---+-----==+---
//----=%+--=@+---=---=-----=+**++**=---------------------=*+****------==---+-----===---
//----*#---*@=---=--==-----=*+#++*+++*=---------------=*#*++#+*+==----+==-+=-----====--
//---=@=---%%----=--=+-----=*+#++*++++***+----------*****+++#**++-----+==-+-------===--
//---%#----%%---==--=+------*+*++*++**+***+**++=+****+==++*+**#-+-----+==-+-------+==--
//--=@=---=%#---==--+*------*++*+*++#+*****++++****+--==*=*****==----===-==-------+==--
//--##----=@*---+=--+*------=++*+*++*++++++*******=-------+***==-----===-==-------+==--
//-=@+----+@=---+=--+#=-----=*+*+*++#++*+++**#*++-+-------+***-+-----+===+--------*==--
//-*@=----*@=---=---+*+------++*+*+*-=++*+***=-+--+--------#**-=-----*====--------*==--
//=%%-----#@---==---=**------++****---------*=----+--------=#=+-----=*==*---------*==--
//=@*-----%@---==---=*#------++*+------=+%@##@+==%%+*+==----+==-----+*+-++++=+++*++==--

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