Language: C++


#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

//Base class for Segment Trees
template <class T>
class segtree_base
{
protected:
	size_t width;
	vector<T> vec;
	T def;
	virtual T query_raw(int l_, int r_, int a_, int b_, int k_) = 0;
public:
	segtree_base(size_t size_, T def_ = T()) : def(def_)
	{
		width = 1;
		while (width < size_)width *= 2;
		vec.resize(width * 2 - 1, def);
	}
	//Ask a query in ranges [left,right)
	T query(int left, int right)
	{
		return query_raw(left, right, 0, width, 0);
	}
	//Get the number of child nodes
	size_t treeWidth()
	{
		return width;
	}
	virtual ~segtree_base() {}
};

struct node
{
	LL P, Q, R;
	node(LL p, LL q, LL r) :
		P(p), Q(q), R(r)
	{}
};

const LL INF = 1145148101919364;

node merge(const node& n1, const node& n2)
{
	return node(
		n1.P + n2.P,
		max(n1.Q + n2.P, n2.Q),
		min(n1.R + n2.P, n2.R)
	);
}

#include <algorithm>
//Range Minimum Tree
class clamp_tree : public segtree_base<node>
{
public:
	clamp_tree(size_t size_) : segtree_base<node>(size_, node(0,-INF,+INF))
	{}

	//Make [index] <= val;
	void update(int index, node val)
	{
		auto &vec = this->vec;
		index += (this->width - 1);
		vec[index] = val;
		while (index > 0)
		{
			index = (index - 1) / 2;
			//vec[index] = std::min(vec[index * 2 + 1], vec[index * 2 + 2], Comp());
			vec[index] = merge(vec[index * 2 + 1], vec[index * 2 + 2]);
		}
	}
private:
	node query_raw(int l_, int r_, int a_, int b_, int k_)override
	{
		const auto &vec = this->vec;
		if (l_ <= a_ && b_ <= r_)
		{
			return vec[k_];
		}
		if (b_ <= l_ || r_ <= a_)
		{
			return this->def;
		}
		int m = (a_ + b_) / 2;
		return merge(
			query_raw(l_, r_, a_, m, k_ + k_ + 1),
			query_raw(l_, r_, m, b_, k_ + k_ + 2));
	}
};

LL X, K;
vector<LL>r, dif;
LL Q;

int main(void)
{
	cin >> X;
	cin >> K;
	r.push_back(0);
	for (int i = 0; i < K; ++i)
	{
		LL rr; cin >> rr;
		dif.push_back(rr - r.back());
		r.push_back(rr);
	}
	clamp_tree clamp(K);
	for (int k = 0; k < K; ++k)
	{
		LL dd = dif[k] * ((k % 2) ? 1 : -1);
		clamp.update(k, node(dd, 0, X));
	}
	cin >> Q;
	for (int q = 0; q < Q; ++q)
	{
		LL t, a;
		cin >> t >> a;
		auto &itr = upper_bound(r.begin(), r.end(), t);
		--itr;
		int index = itr - r.begin();
		auto res = clamp.query(0, index);
		LL sand = a + res.P;
		sand = max(sand, res.Q);
		sand = min(sand, res.R);
		sand += ((index % 2) ? 1 : -1) * (t - *itr);
		sand = max(sand, 0LL);
		sand = min(sand, X);
		cout << sand << endl;
	}
	return 0;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:144:40: error: cannot bind non-const lvalue reference of type '__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >&' to an rvalue of type '__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >'
  144 |                 auto &itr = upper_bound(r.begin(), r.end(), t);
      |                             ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~