| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1320441 | 24ta_tdanh | Happiness (Balkan15_HAPPINESS) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <cstdlib>
// #include "happiness.h"
#define endl '\n'
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define ce cout << endl
#define ALL(A) A.begin(), A.end()
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOR2(i, l, r) for (int i = l; i >= r; i--)
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using str = string;
using ull = unsigned long long;
using ld = long double;
const ll INF = 1e18;
const ll N = 1e12;
const int LOGN = 14;
const int C = 2000;
const int heavy = 500;
const int MOD = 1e9 + 7;
const int Q = 50000;
int dx[] = {0, 1, 0, -1}; // east, south, west, north
int dy[] = {1, 0, -1, 0};
// T_Danh - Tri An High School
struct SegmentTree {
private:
struct NODE {
ll sum = 0;
ll diff = 0;
bool len_one = false;
NODE *left = nullptr, *right = nullptr;
};
NODE *root = new NODE();
ll n;
NODE merge(NODE a, NODE b) {
NODE res;
res.sum = a.sum + b.sum;
res.diff = max( (a.len_one == true ? 0 : a.diff), b.diff - a.sum);
return res;
}
void push(NODE *cur) {
if (!cur->left) cur->left = new NODE();
if (!cur->right) cur->right = new NODE();
}
void update(NODE *cur, ll l, ll r, ll x , int val) {
if (l == r) {
cur->sum += x * val;
cur->diff = x;
cur->len_one = true;
return;
}
push(cur);
ll mid = l + r >> 1;
if (x <= mid) update(cur->left, l, mid, x , val);
else update(cur->right, mid + 1, r, x , val);
NODE res = merge(*(cur->left), *(cur->right));
cur->sum = res.sum;
cur->diff = res.diff;
}
NODE get(NODE *cur, ll l, ll r, ll u, ll v) {
if (u <= l && r <= v) return *cur;
ll mid = l + r >> 1;
push(cur);
if (v <= mid) return get(cur->left, l, mid, u, v);
if (u > mid) return get(cur->right, mid + 1, r, u, v);
return merge(get(cur->left, l, mid, u, v), get(cur->right, mid + 1, r, u, v));
}
public:
SegmentTree(ll n) : n(n) {}
void upd(ll pos , int val) { update(root, 1, n, pos, val); }
bool query(ll u, ll v) {
NODE res = get(root, 1, n, u, v);
return (res.len_one == true || res.diff <= 1);
}
}st(N + 1);
ll sum = 0;
// bool init(int coinsCount, long long maxCoinSize, long long coins[]){
// // FOR(i,0,coinsCount - 1){
// // st.upd(coins[i]);
// // sum += coins[i];
// // }
// // return st.query(1 , min(sum , N));
// }
// bool is_happy(int event, int coinsCount, long long coins[]){
// }
void solve(){
int n , m ;
cin >> n >> m;
int cnt1 = 0 ;
FOR(i,0,n - 1){
ll x;
cin >> x;
sum += x;
st.upd(x , 1);
if(x == 1) cnt1 ++;
}
cout << (cnt1 && st.query(1 , sum)) <<endl;
int q;
cin >> q;
while(q--){
int t, sz;
cin >> t >> sz;
if(t == 1){
FOR(i,0,sz - 1){
ll x;
cin >> x;
st.upd(x , 1);
sum += x;
if(x == 1) cnt1 ++;
}
cout << (cnt1 && st.query(1 , sum)) <<endl;
}
else{
FOR(i, 0 , sz - 1){
ll x ;
cin >> x;
st.upd(x , - 1);
sum -= x;
if(x == 1) cnt1 --;
}
cout << (cnt1 && st.query(1 , sum)) << endl;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1;
while (t--) solve();
return 0;
}