제출 #996667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
996667		SamuellH12	Fish 3 (JOI24_fish3)	C++17	0 / 100	2051 ms	22828 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 = 1e6 + 5;
using namespace std;
#define int ll

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 );
	}
};

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


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;
			minSufix -= V*D;
			A += V*(R-L); //(R-L+1 - 1) // -1 pq não conta com o C
			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 N = (R-L+1);
	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;
			minSufix += V*D;
			A -= V*(R-L+1); //(R-L+1) //sem o -1 pq agora o intervalo já exclui C
			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;

	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;	
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void remove(long long int, bool)':
Main.cpp:78:6: warning: unused variable 'N' [-Wunused-variable]
   78 |  int N = (R-L+1);
      |      ^

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