Submission #1097014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097014		I_am_Polish_Girl	Fish 3 (JOI24_fish3)	C++14	48 / 100	391 ms	65876 KiB

Main

//#pragma target("arch=icelake-server")

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack> 
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <bitset>

using namespace std;

#define int long long

typedef long long ll;
typedef long double ld;

int log_ = 11;
int inf = 4000000007000000007;

long long mod = 1000000007;

int p = 499;

int NADIYA = 39;

struct segment_tree
{
	vector <pair <int, int>> tree;
	int size;
	int size2;
	void init(int n)
	{
		size2 = n;
		size = 1;
		while (size < n)
			size *= 2;
		tree.resize(size * 2, { 0 , 0 });
	}

	void build(int l, int r, int ind)
	{
		if (r - l == 1)
		{
			if (l < size2)
				tree[ind].first = 0;
			return;
		}
		int m = (r + l) / 2;
		build(l, m, ind * 2 + 1);
		build(m, r, ind * 2 + 2);
		tree[ind].first = tree[ind * 2 + 1].first + tree[ind * 2 + 2].first;
	}

	void build(int n)
	{
		init(n);
		//build(0, size, 0);
	}
	/*
	void push(int ind)
	{
		if (tree[ind] != -1)
		{
			tree[ind * 2 + 1] = tree[ind];
			tree[ind * 2 + 2] = tree[ind];
			tree[ind] = -1;
		}
	}*/
	void modified(int l, int r, int ind, int lx, int rx, int v)
	{
		if (r <= lx)
			return;
		if (rx <= l)
			return;

		if (r - l == 1)
		{
			tree[ind].second += v;

			tree[ind].first += v * (r - l);
			return;
		}

		if ((lx <= l) and (r <= rx))
		{
			tree[ind].second += v;

			tree[ind].first += v * (r - l);
			return;
		}
		int m = (r + l) / 2;
		modified(l, m, ind * 2 + 1, lx, rx, v);
		modified(m, r, ind * 2 + 2, lx, rx, v);
		tree[ind].first = (tree[ind * 2 + 1].first + tree[ind * 2 + 2].first) + tree[ind].second * (r - l);
	}
	void modified(int lx, int rx, int v)
	{
		modified(0, size, 0, lx, rx, v);
	}

	int get(int l, int r, int ind, int lx, int rx, int sum)
	{
		if (r <= lx)
			return 0;
		if (rx <= l)
			return 0;

		if (r - l == 1)
		{
			return tree[ind].first + sum * (r - l);
		}

		if ((lx <= l) and (r <= rx))
		{
			return tree[ind].first + sum * (r - l);
		}
		sum += tree[ind].second;

		int m = (r + l) / 2;
		ll g1 = get(l, m, ind * 2 + 1, lx, rx, sum);
		ll g2 = get(m, r, ind * 2 + 2, lx, rx, sum);
		return g1 + g2;
	}
	int get(int l, int r)
	{
		return get(0, size, 0, l, r, 0);
	}
};


vector <int> pref;

int get(int l, int r)
{
	if (l == 0)
		return pref[r];
	else
		return pref[r] - pref[l - 1];
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, d;
	cin >> n >> d;

	vector <int> a(n);

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	int p = 0;
	pref.resize(n);

	for (int i = 0; i < n; i++)
	{
		p += a[i];
		pref[i] = p;
	}

	vector <vector <pair <int, int>>> q(n);

	int q_;
	cin >> q_;

	vector <int> ans(q_);

	for (int i = 0; i < q_; i++)
	{
		int l, r;
		cin >> l >> r;

		l--;
		r--;

		q[r].push_back({ l , i });
	}

	segment_tree st;

	map <int , int> mp;

	mp[0] = inf;

	st.build(n);

	st.modified(0, 1, a[0]);

	for (int i = 1; i < n; i++)
	{
		st.modified(i, i + 1, a[i]);

		if (a[i - 1] <= a[i])
		{
			

			int sz = (a[i] - a[i - 1]);
			int c = (sz / d) + ((sz % d) > 0);

			mp[i] = c;
		}
		else
		{
			int sz = (a[i - 1] - a[i]);
			int c = (sz / d) + ((sz % d) > 0);

			while (c > 0)
			{
				int ind = (*mp.rbegin()).first;
				int x = mp[ind];

				mp.erase(ind);

				if (x <= c)
				{
					st.modified(ind, i , -d * x);

					c -= x;
				}
				else
				{
					st.modified(ind, i , -d * c);

					x -= c;

					mp[ind] = x;
					c = 0;
				}
			}
		}

		for (int j = 0; j < q[i].size(); j++)
		{
			int l = q[i][j].first;
			int indx = q[i][j].second;

			
			if (st.get(l, l + 1) < 0)
			{
				ans[indx] = -1;
				continue;
			}

			ans[indx] = st.get(l, i + 1);

			ans[indx] = (get(l, i) - ans[indx]) / d;
		}
	}

	for (int i = 0; i < q_; i++)
	{
		cout << ans[i] << "\n";
	}
}

/*5
1 2 1
2 3 1
2 4 1
1 5 4
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:245:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  245 |   for (int j = 0; j < q[i].size(); j++)
      |                   ~~^~~~~~~~~~~~~

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