Submission #996672

#	Time	Username	Problem	Language	Result	Execution time	Memory
996672		SamuellH12	Fish 3 (JOI24_fish3)	C++17	0 / 100	2076 ms	60260 KiB

Main

#include <bits/stdc++.h>
#define optimize ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define ALL(x) x.begin(), x.end()
#define endl "\n"
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define INF 0x3f3f3f3f3f3f3f3f
const int MAXN = 3e5 + 5;
using namespace std;
#define int ll

const int MAXLG = 31 - __builtin_clz(MAXN) + 1;

vi fish;
int table[MAXN][MAXLG];

void calc(){
	int N = fish.size();
	for(int i=0; i<N; i++) table[i][0] = fish[i];

	for(int p=1; p < MAXLG; p++)
		for(int i=0; i + (1 << p) <= N; i++)
			table[i][p] = min(table[i][p-1], table[i+(1 << (p-1))][p-1]);
}

int queryst(int l, int r){
	int p = 31 - __builtin_clz(r - l + 1);	//floor log
	return min(table[l][p], table[ r - (1<<p) + 1 ][p]);
}

int bit[MAXN];

void update(int pos, int val){
	for(; pos < MAXN; pos += pos&(-pos))
		bit[pos] += val;
}

int query(int pos){
	int sum = 0;
	for(; pos > 0; pos -= pos&(-pos))
		sum += bit[pos];
	return sum;
}

int querypt(int pos){ return query(pos+1); } //+1 pq idx tá 0-index
void updateSeg(int l, int r, int val){ update(l+1, val), update(r+2, -val); }

const int BLOCK_SZ = 550;

struct Query{
	int l, r, idx;

	Query(int l, int r, int idx) : l(l), r(r), idx(idx) {}
	
	bool operator < (Query q) const {
		if(l / BLOCK_SZ != q.l / BLOCK_SZ) return l < q.l;
		return (l / BLOCK_SZ &1) ? ( r < q.r ) : (r > q.r );
	}
};


int D;
int minSufix = INF;
int A = 0;
int BACK = 0;
int L = 0, R = 0;

int lUpdate(int x, int RR){
	int ans = L;

	int l=L, r=RR, mid;
	while(l<=r)
	{
		mid = (l+r)/2;

		if(queryst(mid, RR) <= x) 
			ans = mid+1, l = mid+1;
		else r = mid-1;
	}

	return ans;
}

void add(int idx, bool sf){
	int C = fish[idx];

	if(sf) // adicionando C no sufixo
	{
		// if(C >= BACK) // OK 
		if(C < BACK)
		{
			int V = (BACK-C + D-1) / D;
			int l = lUpdate(C, R-1);
			// cerr << L << "L R" << R << " | lUpd " << l << endl;	
			A += V*(R-l); //(R-L+1 - 1) // -1 pq não conta com o C
			if(L == l) minSufix -= V*D;
			updateSeg(l, R-1, V);
		}
	}
	else // adicionando C no prefixo
	{
		//if fish[idx] > minSufix
		int V = max(C-minSufix + D-1, 0LL) / D;
		minSufix = C-V*D;
		A += V;
		if(V) updateSeg(idx, idx, V);
	}

	BACK = fish[R];
}

void remove(int idx, bool sf){
	int C = fish[idx];
	BACK = fish[R];

	if(sf) // removendo C do sufixo
	{
		// if(C >= BACK) // ok ok
		if(C < BACK)
		{
			int V = (BACK-C + D-1) / D;
			int l = lUpdate(C, R);
			A -= V*(R-l+1); //(R-L+1) //sem o -1 pq agora o intervalo já exclui C
			if(l == L) minSufix += V*D;
			updateSeg(l, R, -V);
		}
	}
	else // removendo C no prefixo
	{
		// remove os Ds que tava usando
		int V = querypt(idx);
		A -= V;
		updateSeg(idx, idx, -V);

		//restaura o minSufix
		minSufix = fish[L] - querypt(L)*D;
	}
}

int getAnswer(){
	if(minSufix >= 0LL) return A;
	else return -1LL;
}


vector<int> MO(vector<Query> &queries){
	vector<int> ans(queries.size());

	sort(queries.begin(), queries.end());

	L = 0, R = 0;
	BACK = fish[0];
	add(0, false);

	for(auto [l, r, idx] : queries)
	{
		while(l < L) add(--L, false);
		while(r > R) add(++R, true);
		while(l > L) remove(L++, false);
		while(r < R) remove(R--, true);
		
		ans[idx] = getAnswer();
	}

	return ans;
}


int32_t main(){
	optimize;
	int n;
	cin >> n >> D;

	fish = vi(n);
	for(auto &x : fish) cin >> x;
	calc();

	int q;
	cin >> q;

	vector<Query> queries;

	for(int i=0, l, r; i<q; i++)
	{
		cin >> l >> r;
		l--, r--;
		queries.emplace_back(l, r, i);
	}

	auto ans = MO(queries);
	for(auto x : ans) cout << x << endl;
	
	return 0;	
}

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