Problem Background

After dropping biology, 123abc finally got free time to work on something he really interested in. Although soso always told 123abc to devote his time to concentrating in OI, 123abc refused and started searching for a girl – someone who shared his love for algorithms and late-night coding marathons, someone who wouldn’t mind debugging life’s problems with him together.

But alas, life wasn’t a simple binary search.

123abc wandered through the labyrinth of social networks, his heart hoping to find a connection. Yet, every time he thought he had found “the one,” it turned out to be nothing more than a segmentation fault of expectations.

When soso found out, he shook his head and said: “You could have optimized your time complexity by focusing on OI instead.”

123abc just laughed, replying: “Life isn’t always about efficiency, soso. Sometimes, you have to brute force your way to happiness.”

And so, his quest continued, with the hope that one day, he’d find the perfect “runtime partner.”

And, against all odds, he really found one.

She wasn’t just any girl. She was smart, witty, and had a knack for solving problems – both in life and in code. Her username was “456def”, she studies in *, and their first conversation started in a team minicomp in * training, where she corrected a subtle bug in one of 123abc’s solutions.

“You forgot to handle edge cases,” she said. 123abc grinned. “Thanks… maybe you can help me handle mine?”

From there, it was as if their lives compiled perfectly together. They spent nights brainstorming algorithms, debugging each other’s code, and even competing in OI virtual contests. She was the quicksort to his merge sort – different approaches, but both striving for the same goal.

When soso heard about their relationship, he sighed and said: “Well, at least she’s OI-compatible. I guess that’s acceptable.”

But 123abc smiled and replied: “She’s more than compatible, soso. She’s my perfect runtime partner.”

And for the first time, 123abc felt like his life was finally running in O(1) – fast, efficient, and filled with happiness.

It’s the (1/12)-th anniversary (i.e. the 1st month) of 123abc and his girlfriend, 456def! To celebrate this, 123abc decided to go shopping with his girlfriend at the * plaza.

However, as * plaza is too cheap, his girlfriend is not satisfied.

(She expected to go shopping at somewhere like *.)

Problem Statement

Fortunately, as 456def is so nice, she may sometimes be satisfied no matter how cheap her boyfriend was. As 456def is too pretty, the government decided to reform the monetary system and release banknotes with values of all integer numbers from to and print her face on the banknotes. 456def always knows her set of banknotes – let’s assume their values are . All those values are between and and she may possess more than one banknote of a kind. Also, the sequence of values is not ordered in any way. 456def is satisfied if and only if when entering a shop, she may buy any combination of goods with total price equal to any number between and the total sum of her banknotes without changes.

As expected, 456def’s set of banknotes is changing after each purchase and also after each time her boyfriend gives her banknotes – that’s why her satisfaction is variable. There are events. For each event , is the type of the event ( indicates that she received banknotes from her boyfriend and indicates that she has spent some banknotes.) is the number of banknotes she has received/spent. is the banknotes she has received/spent. Your task is to determine whether she is satisfied, initially (before all events), and after each event.

Note that the events are not independent and she felt satisfied when she has no money.

Input

The first line contains two integers, and .

The second line contains integers, .

The third line contains a single integer, .

For the following lines,
Each line starts with two integers, and which are the type of the event and the number of corresponding banknotes, followed by integers, .

Output

On the first line, output a single integer, , which is the satisfaction before all events. (1 for satisfied and 0 for unsatisfied)

On the following lines, output a single integer, which is the satisfaction after event .

Subtasks

Let denote the number of 456def’s banknotes at any given moment.

For all subtasks,

Subtask 1: worth 1% of the total points, .

Subtask 2: worth 4% of the total points, .

Subtask 3: worth 7% of the total points, .

Subtask 4: worth 13% of the total points, .

Subtask 5: worth 16% of the total points, .

Subtask 6: worth 20% of the total points, .

Subtask 7: worth 30% of the total points, .

Subtask 8: worth 9% of the total points, no additional constraints.

Problem Solution:

By 1234567890regis.

The official solution is crap (who likes Necessary & Sufficient Conditions???). I’m going to write my own solution. NO OBSERVATION SOLUTION.

Call the sequence “good” if 456def is satisfied when she has this sequence of money.

Denote the sum of all numbers in the sequence that is less than to be . Obviously to check if the sequence is good you need to check for every , whether . Now we can denote and maintain it, and to check if the sequence is good, we need to query the minimum value of for and see if it is .

Now on to insertion/deletion. When you try adding into the sequence, the calculation of is trivial. But there might cause other s to change. So for all such that , we must add to to maintain it.

And that just obviously lead to Segment Tree. And you’re done. You can discretize and set all to before all the operations.

Accepted Code

In the segment tree:

• tag: number of Active values in the interval
• mn: minimum of all Active values in the interval
• tree: sum of ALL values in the interval (whether active or not)
• lazy: lazy tag of value waiting to add to the entire interval

The segment tree stores the value of . Let be the sum of the Active numbers that is less than , then is defined as . ( is the original, undiscretized value).

Active means whether it is in the set or not.

Everytime you want to see if the array is “good”, you query the minimum of across all Active values. If it is then its bad, reason being that there exists , which indicates so its bad.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
using namespace std;

const int MAXN = 8e5 + 7;
int a[MAXN], e[MAXN], k[MAXN], val[MAXN][7], cnt, to[MAXN], n, m, q;

vector<int> disc;
unordered_map<int, int> mp;

#define lsx (2 * idx)
#define rsx (2 * idx + 1)
#define mid (l + r >> 1)
struct segtree
{
	int tree[MAXN << 2], mn[MAXN << 2], lazy[MAXN << 2], tag[MAXN << 2];
	void pushdown(int l, int r, int idx)
	{
		tree[lsx] += (mid - l + 1) * lazy[idx];
		tree[rsx] += (r - mid) * lazy[idx];
		lazy[lsx] += lazy[idx];
		lazy[rsx] += lazy[idx];
		mn[lsx] += lazy[idx];
		mn[rsx] += lazy[idx];
		lazy[idx] = 0;
	}
	void pushup(int idx)
	{
		tree[idx] = tree[lsx] + tree[rsx];
		tag[idx] = tag[lsx] + tag[rsx];
		if (!tag[idx]) mn[idx] = 0;
		else if (!tag[lsx]) mn[idx] = mn[rsx];
		else if (!tag[rsx]) mn[idx] = mn[lsx];
		else mn[idx] = min(mn[lsx], mn[rsx]);
	}
	void insert(int qidx, int val, int l = 1, int r = cnt, int idx = 1)
	{
		//debug(qidx); debug(val); debug(l); debug(r); debug(idx);
		if (l == r) return tag[idx] += val, mn[idx] = tree[idx], void();
		pushdown(l, r, idx);
		if (qidx <= mid) insert(qidx, val, l, mid, lsx);
		else insert(qidx, val, mid + 1, r, rsx);
		pushup(idx);
	}
	void change(int ql, int qr, int val, int l = 1, int r = cnt, int idx = 1)
	{
		if (r < ql || qr < l) return;
		if (ql <= l && r <= qr) return tree[idx] += (r - l + 1) * val, mn[idx] += val, lazy[idx] += val, void();
		pushdown(l, r, idx);
		change(ql, qr, val, l, mid, lsx);
		change(ql, qr, val, mid + 1, r, rsx);
		pushup(idx);
	}
	int query(int ql, int qr, int l = 1, int r = cnt, int idx = 1)
	{
		if (r < ql || qr < l) return 0;
		if (ql <= l && r <= qr) return tree[idx];
		pushdown(l, r, idx);
		return query(ql, qr, l, mid, lsx) + query(ql, qr, mid + 1, r, rsx);
	}
	void dbg(int l = 1, int r = cnt, int idx = 1)
	{
		debug(idx); debug(l); debug(r); debug(tree[idx]); debug(lazy[idx]); debug(mn[idx]); debug(tag[idx]);
		cout << endl;
		if (l == r) return;
		dbg(l, mid, lsx);
		dbg(mid + 1, r, rsx);
	}
} tr;

signed main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i], disc.push_back(a[i]);
	cin >> q;
	for (int i = 1; i <= q; i++) {
		cin >> e[i] >> k[i];
		for (int j = 1; j <= k[i]; j++) {
			cin >> val[i][j];
			if (e[i] == 1) disc.push_back(val[i][j]);
		}
	}
	sort(disc.begin(), disc.end());
	for (int i : disc)
		if (mp.find(i) == mp.end())
			mp[i] = ++cnt, to[cnt] = i;
	for (int i = 1; i <= cnt; i++) tr.change(i, i, 1 - to[i]);
	for (int i = 1; i <= n; i++) {
		int x = a[i];
		tr.insert(mp[x], 1);
		tr.change(mp[x] + 1, cnt, x);
	}
	cout << (tr.mn[1] >= 0 ? 1 : 0) << endl;
	for (int i = 1; i <= q; i++) {
		for (int j = 1; j <= k[i]; j++) {
			int x = val[i][j];
			tr.insert(mp[x], e[i]);
			tr.change(mp[x] + 1, cnt, x * e[i]);
		}
		cout << (tr.mn[1] >= 0 ? 1 : 0) << endl;
	}
}

—THE END—