oj.uz

Submission #409712

# Submission time Handle Problem Language Result Execution time Memory
409712 2021-05-21T11:37:35 Z codebuster_10 Happiness (Balkan15_HAPPINESS) C++17
30 / 100
 708 ms 524292 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, l, r;// node cover [tl,tr], also lazy is not added to current node;
	Node() : sum(0), l(-1), r(-1) {}
};
 
const int BEST = 1e6;
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; //rd(n,M);
  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

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 17 ms 39372 KB Output is correct
2 Correct 18 ms 39360 KB Output is correct
3 Correct 18 ms 39372 KB Output is correct
4 Correct 18 ms 39436 KB Output is correct
5 Correct 18 ms 39408 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 39372 KB Output is correct
2 Correct 18 ms 39360 KB Output is correct
3 Correct 18 ms 39372 KB Output is correct
4 Correct 18 ms 39436 KB Output is correct
5 Correct 18 ms 39408 KB Output is correct
6 Correct 19 ms 39372 KB Output is correct
7 Correct 19 ms 39404 KB Output is correct
8 Correct 44 ms 39692 KB Output is correct
9 Correct 43 ms 39640 KB Output is correct
10 Correct 41 ms 39620 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 39372 KB Output is correct
2 Correct 18 ms 39360 KB Output is correct
3 Correct 18 ms 39372 KB Output is correct
4 Correct 18 ms 39436 KB Output is correct
5 Correct 18 ms 39408 KB Output is correct
6 Runtime error 708 ms 524292 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 39372 KB Output is correct
2 Correct 18 ms 39360 KB Output is correct
3 Correct 18 ms 39372 KB Output is correct
4 Correct 18 ms 39436 KB Output is correct
5 Correct 18 ms 39408 KB Output is correct
6 Correct 19 ms 39372 KB Output is correct
7 Correct 19 ms 39404 KB Output is correct
8 Correct 44 ms 39692 KB Output is correct
9 Correct 43 ms 39640 KB Output is correct
10 Correct 41 ms 39620 KB Output is correct
11 Runtime error 708 ms 524292 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -