oj.uz

Submission #916982

# Submission time Handle Problem Language Result Execution time Memory
916982 2024-01-26T22:04:33 Z Nonoze Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1144 ms 467116 KB 
#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)x.size()


struct node
{
	int left, right;
	int sum, lazy;
	int l, r;
	int maxi;
	node() {
		sum=0, left=-1, right=-1, maxi=0;
	}
};

vector<node> st;

void update(int root, int left, int right, int qLeft, int qRight, int nValue)
{
	if (left>qRight || right<qLeft) return;
	if (left>=qLeft && right<=qRight) {
		st[root].sum+=left*nValue;
		if (st[root].sum!=0) st[root].maxi=left;
		else st[root].maxi=0;
		return;
	}
	int mid=(left+right)/2;
	if (mid>=qLeft) {
		if (st[root].left==-1) {
			st[root].left = sz(st);
			st.push_back(node());
			st[ st[root].left ].l=left, st[ st[root].left ].r=mid;
		}
		update(st[root].left, left, mid, qLeft, qRight, nValue);
	}
	if (mid<qRight) {
		if (st[root].right==-1) {
			st[root].right = sz(st);
			st.push_back(node());
			st[ st[root].right ].l=mid+1, st[ st[root].right ].r=right;
		}
		update(st[root].right, mid+1, right, qLeft, qRight, nValue);
	}
	st[root].sum=0;
	if (st[root].left!=-1) st[root].sum+=st[ st[root].left ].sum;
	if (st[root].right!=-1) st[root].sum+=st[ st[root].right ].sum;
	st[root].maxi=0;
	if (st[root].right!=-1) {
		st[root].maxi=max(0LL, st[ st[root].right ].maxi-(st[root].left!=-1?st[st[root].left].sum:0));
	}
	if (st[root].left!=-1){
		st[root].maxi=max(st[ st[root].left ].maxi, st[root].maxi);
	}
}

int mx;

bool init(signed n, long long mxx, long long coins[]) {
	mx=mxx;
	st.push_back(node());
	st[0].l=1, st[0].r=mx+1;
	for (int i=0; i<n; i++) update(0, 1, mx+1, coins[i], coins[i], 1);
	return st[0].maxi<=1;
}
bool is_happy(signed event, signed n, long long coins[]) {
	for (int i=0; i<n; i++) update(0, 1, mx+1, coins[i], coins[i], event);
	return st[0].maxi<=1;
}

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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 3 ms 2388 KB Output is correct
7 Correct 4 ms 5840 KB Output is correct
8 Correct 29 ms 29668 KB Output is correct
9 Correct 25 ms 31104 KB Output is correct
10 Correct 23 ms 29892 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 278 ms 59304 KB Output is correct
7 Correct 262 ms 60760 KB Output is correct
8 Correct 282 ms 58696 KB Output is correct
9 Correct 539 ms 60056 KB Output is correct
10 Correct 556 ms 59304 KB Output is correct
11 Correct 165 ms 58780 KB Output is correct
12 Correct 186 ms 60064 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 3 ms 2388 KB Output is correct
7 Correct 4 ms 5840 KB Output is correct
8 Correct 29 ms 29668 KB Output is correct
9 Correct 25 ms 31104 KB Output is correct
10 Correct 23 ms 29892 KB Output is correct
11 Correct 278 ms 59304 KB Output is correct
12 Correct 262 ms 60760 KB Output is correct
13 Correct 282 ms 58696 KB Output is correct
14 Correct 539 ms 60056 KB Output is correct
15 Correct 556 ms 59304 KB Output is correct
16 Correct 165 ms 58780 KB Output is correct
17 Correct 186 ms 60064 KB Output is correct
18 Correct 740 ms 467116 KB Output is correct
19 Correct 746 ms 466272 KB Output is correct
20 Correct 1144 ms 465524 KB Output is correct
21 Correct 638 ms 234388 KB Output is correct
22 Correct 299 ms 64396 KB Output is correct
23 Correct 265 ms 64492 KB Output is correct
24 Correct 703 ms 466768 KB Output is correct