oj.uz

Submission #409709

# Submission time Handle Problem Language Result Execution time Memory
409709 2021-05-21T11:30:05 Z codebuster_10 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1442 ms 524288 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 = 8e6;
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;
  vt<int> a(n); 
  f(i,0,n) a[i] = coins[i];
  W = accumulate(all(a),int(0));
	for(auto i : a){
		update(1,i,i,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; 
		vt<int> b(N);
		f(i,0,N) b[i] = coins[i];
		W -= accumulate(all(b),int(0));
		for(auto i : b){
			update(1,i,i,-i);
		}
	}else{
		int N = coinsCount; 
		vt<int> b(N);
		f(i,0,N) b[i] = coins[i];
		W += accumulate(all(b),int(0));
		for(auto i : b){
			update(1,i,i,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 133 ms 313276 KB Output is correct
2 Correct 130 ms 313372 KB Output is correct
3 Correct 132 ms 313364 KB Output is correct
4 Correct 127 ms 313324 KB Output is correct
5 Correct 133 ms 313368 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 313276 KB Output is correct
2 Correct 130 ms 313372 KB Output is correct
3 Correct 132 ms 313364 KB Output is correct
4 Correct 127 ms 313324 KB Output is correct
5 Correct 133 ms 313368 KB Output is correct
6 Correct 131 ms 313380 KB Output is correct
7 Correct 136 ms 313312 KB Output is correct
8 Correct 158 ms 313652 KB Output is correct
9 Correct 154 ms 313688 KB Output is correct
10 Correct 148 ms 313668 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 313276 KB Output is correct
2 Correct 130 ms 313372 KB Output is correct
3 Correct 132 ms 313364 KB Output is correct
4 Correct 127 ms 313324 KB Output is correct
5 Correct 133 ms 313368 KB Output is correct
6 Correct 629 ms 317484 KB Output is correct
7 Correct 650 ms 317468 KB Output is correct
8 Correct 649 ms 317500 KB Output is correct
9 Correct 845 ms 318744 KB Output is correct
10 Correct 823 ms 318808 KB Output is correct
11 Correct 361 ms 317400 KB Output is correct
12 Correct 369 ms 317344 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 313276 KB Output is correct
2 Correct 130 ms 313372 KB Output is correct
3 Correct 132 ms 313364 KB Output is correct
4 Correct 127 ms 313324 KB Output is correct
5 Correct 133 ms 313368 KB Output is correct
6 Correct 131 ms 313380 KB Output is correct
7 Correct 136 ms 313312 KB Output is correct
8 Correct 158 ms 313652 KB Output is correct
9 Correct 154 ms 313688 KB Output is correct
10 Correct 148 ms 313668 KB Output is correct
11 Correct 629 ms 317484 KB Output is correct
12 Correct 650 ms 317468 KB Output is correct
13 Correct 649 ms 317500 KB Output is correct
14 Correct 845 ms 318744 KB Output is correct
15 Correct 823 ms 318808 KB Output is correct
16 Correct 361 ms 317400 KB Output is correct
17 Correct 369 ms 317344 KB Output is correct
18 Runtime error 1442 ms 524288 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -