oj.uz

Submission #409730

# Submission time Handle Problem Language Result Execution time Memory
409730 2021-05-21T11:57:55 Z codebuster_10 Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1692 ms 516356 KB 
#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 = 1.62e7;
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:157:31: warning: 'A' defined but not used [-Wunused-variable]
  157 | static long long coins[NMAX], A[5];
      |                               ^
happiness.cpp:157:18: warning: 'coins' defined but not used [-Wunused-variable]
  157 | static long long coins[NMAX], A[5];
      |                  ^~~~~
happiness.cpp:156:18: warning: 'M' defined but not used [-Wunused-variable]
  156 | static long long M;
      |                  ^
happiness.cpp:155:15: warning: 'Q' defined but not used [-Wunused-variable]
  155 | static int N, Q;
      |               ^
happiness.cpp:155:12: warning: 'N' defined but not used [-Wunused-variable]
  155 | static int N, Q;
      |            ^
grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 507484 KB Output is correct
2 Correct 214 ms 507440 KB Output is correct
3 Correct 242 ms 507488 KB Output is correct
4 Correct 217 ms 507508 KB Output is correct
5 Correct 216 ms 507552 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 507484 KB Output is correct
2 Correct 214 ms 507440 KB Output is correct
3 Correct 242 ms 507488 KB Output is correct
4 Correct 217 ms 507508 KB Output is correct
5 Correct 216 ms 507552 KB Output is correct
6 Correct 229 ms 507476 KB Output is correct
7 Correct 218 ms 507448 KB Output is correct
8 Correct 249 ms 507588 KB Output is correct
9 Correct 236 ms 507640 KB Output is correct
10 Correct 236 ms 507696 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 507484 KB Output is correct
2 Correct 214 ms 507440 KB Output is correct
3 Correct 242 ms 507488 KB Output is correct
4 Correct 217 ms 507508 KB Output is correct
5 Correct 216 ms 507552 KB Output is correct
6 Correct 724 ms 508420 KB Output is correct
7 Correct 686 ms 508428 KB Output is correct
8 Correct 704 ms 508536 KB Output is correct
9 Correct 891 ms 508488 KB Output is correct
10 Correct 851 ms 508568 KB Output is correct
11 Correct 445 ms 507652 KB Output is correct
12 Correct 426 ms 507632 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 507484 KB Output is correct
2 Correct 214 ms 507440 KB Output is correct
3 Correct 242 ms 507488 KB Output is correct
4 Correct 217 ms 507508 KB Output is correct
5 Correct 216 ms 507552 KB Output is correct
6 Correct 229 ms 507476 KB Output is correct
7 Correct 218 ms 507448 KB Output is correct
8 Correct 249 ms 507588 KB Output is correct
9 Correct 236 ms 507640 KB Output is correct
10 Correct 236 ms 507696 KB Output is correct
11 Correct 724 ms 508420 KB Output is correct
12 Correct 686 ms 508428 KB Output is correct
13 Correct 704 ms 508536 KB Output is correct
14 Correct 891 ms 508488 KB Output is correct
15 Correct 851 ms 508568 KB Output is correct
16 Correct 445 ms 507652 KB Output is correct
17 Correct 426 ms 507632 KB Output is correct
18 Correct 1330 ms 508504 KB Output is correct
19 Correct 1354 ms 508428 KB Output is correct
20 Correct 1692 ms 516356 KB Output is correct
21 Correct 1079 ms 513340 KB Output is correct
22 Correct 596 ms 513492 KB Output is correct
23 Correct 599 ms 514072 KB Output is correct
24 Correct 1325 ms 513908 KB Output is correct