Submission #1221400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221400		WH8	Fish 3 (JOI24_fish3)	C++20	28 / 100	509 ms	63088 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define f first
#define s second
#define pll pair<int,int>
#define pb push_back
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define ld long double

struct node {
	int s, e, m, v, lz;
	node *l, *r;
	node (int S, int E){
		s=S, e=E, m=(s+e)/2, v=0, lz=0;
		if(s!=e){
			l=new node(s, m);
			r=new node(m+1, e);
		}
	}
	void prop(){
		if(s==e or lz==0)return;
		l->v+=(l->e - l->s +1) * lz, r->v+=(r->e-r->s+1)*lz, l->lz+=lz, r->lz+=lz;
		lz=0;
	}
	int combine(int a, int b){
		return a+b;
	}
	void upd(int S, int E, int V){
		if((S==s and E==e) or s==e){
			v+=(e-s+1) * V;
			lz+=V;
			return;
		}
		prop();
		if (E<=m) l->upd(S,E,V);
		else if (S>m) r->upd(S,E,V);
		else l->upd(S,m,V),r->upd(m+1,E,V);
		v=combine(l->v,r->v);
	}
	int qry(int S,int E){
		if((S==s and E==e) or s==e){
			return v;
		}
		prop();
		if(E<=m)return l->qry(S,E);
		if(S>m)return r->qry(S,E);
		return combine(l->qry(S,m),r->qry(m+1,E));
	}
} *root;

int n,d;
int c[300005];
int ans[300005];
int qq;

int val(int x){
	return c[x] - d * root->qry(x, x);
}

signed main(){
	cin>>n>>d;
	for(int i=1;i<=n;i++){
		cin>>c[i];
	}
	root=new node(0,n);
	//~ root=new node(0,5);
	//~ root->upd(2, 3, 5);
	//~ root->upd(1, 5, 5);
	//~ cout<<root->qry(0,5);
	//~ return 0;
	c[0]=-1e12;
	vector<pair<int,int>> q;
	q.push_back({0,0});
	cin>>qq;
	vector<tuple<int,int,int>> qs;
	for(int i=0;i<qq;i++){
		int l,r;cin>>l>>r;
		qs.push_back({r,l,i});
	}
	sort(qs.begin(),qs.end());
	int qptr=0;
	for(int i=1;i<=n;i++){
		//~ cout<<"start of " << i <<endl;
		//~ for (auto it : q){
			//~ printf("| %lld,  %lld to %lld, %lld |", it.f, val(it.f), it.s, val(it.s));
			//~ cout<<endl;
		//~ }
		int bk, cc;
		cc=c[i], bk=val(q.back().s);
		while(bk > cc){
			int mvs=(bk-c[i])/d + ((bk-c[i])%d?1:0);
			//~ printf("moves needed is %lld\n", mvs);
			root->upd(q.back().f, q.back().s, mvs);
			cc=val(q.back().f);
			q.pop_back();
			bk=val(q.back().s);
		}
		q.push_back({q.back().s+1, i});
		while(qptr < qq and g0(qs[qptr])==i){
			auto [r, l, ansind] = qs[qptr];
			int fv = val(l);
			if (fv < 0) ans[ansind]=-1;
			else ans[ansind]=root->qry(l, r);
			qptr++;
		}
		//~ cout<<"end of " << i <<endl;
		//~ for (auto it : q){
			//~ printf("| %lld,  %lld to %lld, %lld |", it.f, val(it.f), it.s, val(it.s));
			//~ cout<<endl;
		//~ }
		//~ for(int j=1;j<=n;j++){
			//~ cout<<root->qry(j,j)<<" ";
		//~ }
		//~ cout<<endl;
	}
	for(int i=0;i<qq;i++){
		cout<<ans[i]<<"\n";
	}
}

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