Submission #1601572

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int mx[N << 2], mn[N << 2], add[N << 2], val[N << 2];
#define mid ((l + r) >> 1)

int X, k, q, n;
vector< pair<int,int> > Z;
int pos[N];
int ans[N];

void push(int v, int l, int r) {
	if (l > r) return;
	if (l < r) {
		if (val[v] == -1) {
			add[v << 1] += add[v], add[v << 1 | 1] += add[v];
		} else {
			add[v << 1] = add[v], add[v << 1 | 1] = add[v];
			val[v << 1] = val[v], val[v << 1 | 1] = val[v];
		}
	}
	if (val[v] == -1) {
		mx[v] += add[v], mn[v] += add[v];
	} else {
		mx[v] = mn[v] = val[v] + add[v];
	}
	val[v] = -1; add[v] = 0;
}

void upd(int v, int l, int r, int L, int R, int x, int type) {
	push(v, l, r);
	if (l > r || R < l || L > r) return;
	if (L <= l && r <= R) {
		if (type == 0) val[v] = x; else add[v] = x;
		push(v, l, r);
		return;
	}
	upd(v << 1, l, mid, L, R, x, type); upd(v << 1 | 1, mid + 1, r, L, R, x, type);
	mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
	mn[v] = min(mn[v << 1], mn[v << 1 | 1]);
}

int lef(int v, int l, int r, int x) {
	if (l == r) {
		if (mn[v] >= x) return 0;
		else return l;
	}
	push(v << 1, l, mid); push(v << 1 | 1, mid + 1, r);
	if (mn[v << 1 | 1] < x) return lef(v << 1 | 1, mid + 1, r, x);
	else return lef(v << 1, l, mid, x);
}

int rig(int v, int l, int r, int x) {
	if (l == r) {
		if (mx[v] <= x) return (q + 1);
		else return l;
	}
	push(v << 1, l, mid); push(v << 1 | 1, mid + 1, r);
	if (mx[v << 1] > x) return rig(v << 1, l, mid, x);
	else return rig(v << 1 | 1, mid + 1, r, x);
}

int get(int v, int l, int r, int pos) {
	push(v, l, r);
	if (l > r || r < pos || l > pos) return 0;
	if (l == r) return mx[v];
	return max(get(v << 1, l, mid, pos), get(v << 1 | 1, mid + 1, r, pos));
}

struct query {
	int time; int tp; int a; int id;
	bool operator < (const query &other) const {
		return time < other.time;
	}
} v[N << 1];

void build(int v, int l, int r) {
	if (l > r) return;
	if (l == r) {
		mx[v] = mn[v] = Z[l-1].first;
		add[v] = 0; val[v] = -1;
		return;
	}
	build(v << 1, l, mid); build(v << 1 | 1, mid + 1, r);
	mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
	mn[v] = min(mn[v << 1], mn[v << 1 | 1]);
	add[v] = 0; val[v] = -1;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> X >> k;
	for (int i = 1; i <= k; ++i) cin >> v[i].time, v[i].tp = 'r';
	cin >> q;
	for (int i = 1 + k; i <= q + k; ++i) {
		cin >> v[i].time >> v[i].a, v[i].tp = 't', v[i].id = i - k;
		Z.push_back(make_pair(v[i].a, i - k));
	}

	sort(v + 1, v + k + q + 1);
	sort(Z.begin(), Z.end());
	for (int i = 0; i < (int)Z.size(); ++i) {
		pos[Z[i].second] = i + 1;
	}

	build(1, 1, q);
	n = k + q;

	int upper = 1;
	int lst = 0;
	for (int i = 1; i <= n; ++i) {
		int T = v[i].time - lst;
		lst = v[i].time;
		if (upper == 1) {
			int ll = lef(1, 1, q, T);
			upd(1, 1, q, 1, ll, 0, 0);
			upd(1, 1, q, ll + 1, q, -T, 1);
		} else {
			int rr = rig(1, 1, q, X - T);
			upd(1, 1, q, rr, q, X, 0);
			upd(1, 1, q, 1, rr - 1, T, 1);
		}

		if (v[i].tp == 'r') upper ^= 1;
		else {
			ans[v[i].id] = get(1, 1, q, pos[v[i].id]);
		}
	}	

	for (int i = 1; i <= q; ++i) {
		printf("%d\n", ans[i]);
	}
}

Submission Info

Judge Result