Submission #1267612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267612		namhh	Fish 3 (JOI24_fish3)	C++20	0 / 100	104 ms	16756 KiB

Main

#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 = 2e5+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;
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){
	int mid = (l+r)/2;
	down(id,l,mid,r);
	if(l > v || r < u) return 0;
	if(l >= u && r <= v) return st[id];
	return get(2*id,l,mid,u,v)+get(2*id+1,mid+1,r,u,v);
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> d;
	for(int i = 1; i <= n; i++){
		cin >> c[i];
		if(i >= 2) pre[i] = pre[i-1]+((c[i-1]-c[i]) % d+d) % d;
	}
	cin >> q;
	for(int i = 1; i <= q; i++){
		int l,r;
		cin >> l >> r;
		rem[r].push_back({l,i});
	}
	int mn = 1;
	for(int i = 1; i <= n; i++){
		doan cur = {i,i,c[i],c[i]};
		while(emilia.size()){
			auto it = emilia.back();
			if(it.r < mn) break;
			if(it.vr <= cur.vl){
				if(cur.vl-it.vr < d){
					cur = {it.l,i,it.vl,c[i]};
				    emilia.pop_back();
				}
				else break;
			}
			else{
				int need = (it.vr-cur.vl+d-1)/d;
				update(1,1,n,it.l,it.r,need);
				//cout << i << " " << it.l << " " << it.r << " " << need << "\n";
				if(it.vl-d*need >= 0){
				    cur = {it.l,i,it.vl-d*need,c[i]};
				    emilia.pop_back();
				}
				else{
					mn = lower_bound(pre+1,pre+n+1,pre[it.l]+d*need-it.vl)-pre;
					emilia.pop_back();
					cur = {mn,i,pre[it.l]+d*need-it.vl,c[i]};
					break;
				}
			}
		}
		emilia.push_back(cur);
		for(auto it: rem[i]){
			if(it.fi < mn) ans[it.se] = -1;
			else ans[it.se] = get(1,1,n,it.fi,i);
		}
	}
	for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

//-----+--+----+-==-=*==--=+----------==----------------+=-----==-=+-==----------------
//---===+=----+=----=*=+=*+----------==-----------+=-----==-----==--+-+----------------
//---+=**=-=+---------***+----=------=-------------=-------+-----==-+--=---------------
//----*+-+++**++------=#+----===-----=-------------=-------==-----+-=+=-+--------------
//----++#***+*+++-----=+-----=-=----+---------------+-------+=-----*=-==-+-------------
//---+=+**++**++++==++*=-----===----+---------------+----=---=-----=*+*=-==------------
//---++**==+--++++++***-----+-+-----+---------------==---==--==-----+**---+------------
//----++*#=-+++***+***------+-+-----+----------------=----+---*+=---=*#=-=-+-----------
//-----=**+++*+++**%++-----=--+-----+----------------=----*=--==+==++***-=+==----------
//-------**#**++*%%@==-----=--+-----+-------------=+++++=-+=---+=+=-=+**--+++----------
//---------====+@@%@-=-----+--+--=+++++--------------=----+==--===---+*---+==+---------
//-----------=@*%%%%-=-----+=-==-----=---------------=----+--=-==+-=-=*----++==--------
//----------%#=%=#%%==-----=+--=-----=---------------+----+--===*=*==**=---+-++--------
//--------+@++@=*@%*-=-----=+=-=-----==-------------++-*%%%***=++-+=-+-+---=-===-------
//-------#%-=%=+@%@+-=-----=+=--+++*==*=------------**@*##%*--=-+-----=+---==-+==------
//------=%+-=%=%*@@--=-----=*#*=+*###@%*---------=+*++%***##=-+-+------+---==-=+=------
//-------%*-=%@+@@+-*=-----+-=--@##*##=+==----------=-#*#***-==-+------+---==--++------
//-------+@=+@@*@*-=-=-----=-==-*#%*##=----------------++=+=----+------+---==--==+-----
//--------%@@%%@*=--+=-----=---+=+#==*-------------------==-----+------+---==---=+-----
//----------%+=#-=--==-----+-------===--------------------------*------+---==---+==----
//---------##-%+-=---=-----++----------------------------------=*------=---==---=+=----
//--------=#-*@=-=---=-----**=----------------=----------------+*------=---==----++----
//-------=@==%*-==---=-----++*---------------------------------*+------+---==----++=---
//------=%*-=@--==---=-----+++*-------------------------------**=------+---==----==+---
//------*#--##--==---=-----+++*+--------------------+--------+**=------+---=-----==+---
//-----=@=--@*---=---=-----+++#+*=--------=+=----=+=-------=#+**-------+---+-----==+---
//----=%+--=@+---=---=-----=+**++**=---------------------=*+****------==---+-----===---
//----*#---*@=---=--==-----=*+#++*+++*=---------------=*#*++#+*+==----+==-+=-----====--
//---=@=---%%----=--=+-----=*+#++*++++***+----------*****+++#**++-----+==-+-------===--
//---%#----%%---==--=+------*+*++*++**+***+**++=+****+==++*+**#-+-----+==-+-------+==--
//--=@=---=%#---==--+*------*++*+*++#+*****++++****+--==*=*****==----===-==-------+==--
//--##----=@*---+=--+*------=++*+*++*++++++*******=-------+***==-----===-==-------+==--
//-=@+----+@=---+=--+#=-----=*+*+*++#++*+++**#*++-+-------+***-+-----+===+--------*==--
//-*@=----*@=---=---+*+------++*+*+*-=++*+***=-+--+--------#**-=-----*====--------*==--
//=%%-----#@---==---=**------++****---------*=----+--------=#=+-----=*==*---------*==--
//=@*-----%@---==---=*#------++*+------=+%@##@+==%%+*+==----+==-----+*+-++++=+++*++==--

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