| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1206633 | goulthen | Happiness (Balkan15_HAPPINESS) | C++20 | 0 ms | 0 KiB |
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define per(i, b, a) for (int i = b; i >= a; --i)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define lsb(x) (x)&(-x)
void setIO(string name = "") {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
if (!name.empty()) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
ll fexp(ll a, ll b, ll m) {
if (b == 0) return 1LL;
ll p = a;
ll ans = 1;
while (b > 0) {
if (b % 2 != 0) ans = (ans*p)%m;
p = (p*p)%m;
b >>= 1;
}
return ans;
}
const int MAXN = 2e5+10;
const int INF = 1e18 + 5;
const int MOD = 1e9+7;
struct Node {
int v = 1;
int lazy = 0;
Node *l = nullptr;
Node *r = nullptr;
};
struct Seg3 {
Node *root = new Node;
void apply(Node*cur, int x) {
(cur->v) += x;
(cur->lazy) += x;
}
void flush(Node *cur, int l, int r) {
if ((cur->l) == nullptr) (cur->l) = new Node;
if ((cur->r) == nullptr) (cur->r) = new Node;
if (l!=r) {
apply((cur->l), (cur->lazy));
apply((cur->r), (cur->lazy));
}
(cur->lazy) = 0;
}
int join(int a, int b) {
return {min(a, b)};
}
void update(Node *cur, int l, int r, int tl, int tr, int x) {
if (tr < l || tl > r) return;
if (l>=tl && r <= tr) {
apply(cur, x);
return;
}
flush(cur,l,r);
int mid =(l+r)>>1;
update((cur->l),l,mid,tl,tr,x);
update((cur->r),mid+1,r,tl,tr,x);
(cur->v) = join((cur->l)->v,(cur->r)->v);
}
int query(Node *cur, int l, int r, int tl, int tr) {
if (tr < l || tl > r) return INF;
flush(cur,l,r);
if (l >= tl && r <= tr) return (cur-> v);
int mid = (l+r)>>1;
return join(query((cur->r),mid+1,r, tl,tr), query((cur->l), l, mid, tl,tr));
}
};
void solve() {
int n,m,q;
cin >> n >> m;
Seg3 seg;
int s = 0;
int cnt1 = 0;
rep(i,1,n) {
int x;cin >> x;
s+=x;
if (x==1) cnt1++;
seg.update(seg.root,1,m,x+1,m,x);
seg.update(seg.root,1,m,x,x,-x);
}
cin >> q;
auto ok = [&]() {
int mn = seg.query(seg.root,1,m,1,s);
cout << (cnt1>0 && mn >= 0) << '\n';
};
ok();
while (q--) {
int tp, h;
cin >> tp >> h;
vector<int> c(h);
for (int &v : c) cin >> v;
for (const int &x : c) {
s += x*tp;
if (x==1) cnt1+=tp;
seg.update(seg.root,1,m,x+1,m,x*tp);
seg.update(seg.root,1,m,x,x,-x*tp);
}
ok();
}
}
int32_t main() {
setIO();
int tt = 1;
//cin >> tt;
while (tt-- > 0) solve();
}