#include <bits/stdc++.h>
using namespace std ;
#define int int64_t //be careful about this
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)
#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound
#define UB upper_bound
#define PQ priority_queue
#define sz(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem0(a) memset(a, 0, sizeof(a))
#define mem1(a) memset(a, -1, sizeof(a))
template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
/*
Description :- Sparse lazy segment tree
Source :- https://usaco.guide/plat/sparse-seg?lang=cpp
Verification :- https://oj.uz/submission/409297
*/
struct Node {
int sum, tl, tr;
#undef int
int l, r;// node cover [tl,tr], also lazy is not added to current node;
#define int int64_t
Node() : sum(0), l(-1), r(-1) {}
};
const int BEST = 1e7;
Node st[BEST];
int cnt = 2;
void update(int x, int l, int r, int val) {
if (l == st[x].tl && r == st[x].tr) {
st[x].sum += val;
assert(l == r);
} else {
int mid = (st[x].tl + st[x].tr) / 2;
if (st[x].l == -1) {
st[x].l = cnt++;
st[st[x].l].tl = st[x].tl;
st[st[x].l].tr = mid;
}
if (st[x].r == -1) {
st[x].r = cnt++;
st[st[x].r].tl = mid + 1;
st[st[x].r].tr = st[x].tr;
}
if (l > mid) update(st[x].r, l, r, val);
else if (r <= mid) update(st[x].l, l, r, val);
else {
update(st[x].l, l, mid, val);
update(st[x].r, mid + 1, r, val);
}
st[x].sum = st[st[x].l].sum + st[st[x].r].sum;
}
}
int query(int x, int l, int r) {
if (l <= st[x].tl && st[x].tr <= r) return st[x].sum;
else {
int mid = (st[x].tl + st[x].tr) / 2;
if (st[x].l == -1) {
st[x].l = cnt++;
st[st[x].l].tl = st[x].tl;
st[st[x].l].tr = mid;
}
if (st[x].r == -1) {
st[x].r = cnt++;
st[st[x].r].tl = mid + 1;
st[st[x].r].tr = st[x].tr;
}
if (l > mid) return query(st[x].r, l, r);
else if (r <= mid) return query(st[x].l, l, r);
else return query(st[x].l, l, r) + query(st[x].r, l, r);
}
}
int W;
bool go(){
for(int x = 1; x < W;){
int res = query(1,1,x);
if(res < x){
return false;
}
x = res + 1;
}
return true;
}
#undef int
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
#define int int64_t
int n = coinsCount, M = maxCoinSize;
st[1].tl = 1, st[1].tr = M;
f(i,0,n){
update(1,coins[i],coins[i],coins[i]);
W += coins[i];
}
return go();
}
#undef int
bool is_happy(int event, int coinsCount, long long coins[]) {
#define int int64_t
int t = event;
if(t == -1){
int N = coinsCount;
f(i,0,N){
update(1,coins[i],coins[i],-coins[i]);
W -= coins[i];
}
}else{
int N = coinsCount;
f(i,0,N){
update(1,coins[i],coins[i],coins[i]);
W += coins[i];
}
}
return go();
#undef int
}
#define NMAX 200000
#define QMAX 100000
static int N, Q;
static long long M;
static long long coins[NMAX], A[5];
int main()
{
int i, d;
long long max_code;
scanf("%d%lld", &N, &M);
for (i = 0; i < N; ++i) {
scanf("%lld", &coins[i]);
}
if (init(N, M, coins))printf("1\n");
else printf("0\n");
scanf("%d", &Q);
for (i = 0; i < Q; ++i) {
int ck, c;
scanf("%d%d", &ck, &c);
for (int j = 0; j < c; j++) {
scanf("%lld", &A[j]);
}
if (is_happy(ck, c, A))printf("1\n");
else printf("0\n");
}
return 0;
}
Compilation message
happiness.cpp: In function 'int main()':
happiness.cpp:161:9: warning: unused variable 'd' [-Wunused-variable]
161 | int i, d;
| ^
happiness.cpp:162:12: warning: unused variable 'max_code' [-Wunused-variable]
162 | long long max_code;
| ^~~~~~~~
happiness.cpp:164:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
164 | scanf("%d%lld", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~~~
happiness.cpp:166:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
166 | scanf("%lld", &coins[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~
happiness.cpp:170:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
170 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
happiness.cpp:173:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
173 | scanf("%d%d", &ck, &c);
| ~~~~~^~~~~~~~~~~~~~~~~
happiness.cpp:175:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
175 | scanf("%lld", &A[j]);
| ~~~~~^~~~~~~~~~~~~~~
grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
16 | long long max_code;
| ^~~~~~~~
/usr/bin/ld: /tmp/ccgDVw6H.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccduf22G.o:happiness.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
