oj.uz

Submission #916976

# Submission time Handle Problem Language Result Execution time Memory
916976 2024-01-26T21:46:16 Z Nonoze Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 858 ms 524288 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 (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;
	}
	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;
	}
	if (mid>=qLeft) update(st[root].left, left, mid, qLeft, qRight, nValue);
	if (mid<qRight) update(st[root].right, mid+1, right, qLeft, qRight, nValue);
	st[root].sum=st[ st[root].left ].sum + st[ st[root].right ].sum;
	st[root].maxi=st[ st[root].right ].maxi - st[ st[root].left ].sum;
	st[root].maxi=max(st[ st[root].left ].maxi, st[root].maxi);
	st[root].maxi=max(st[root].maxi, 0LL);
}

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 1 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 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 KB Output is correct
6 Correct 5 ms 5584 KB Output is correct
7 Correct 5 ms 8140 KB Output is correct
8 Correct 40 ms 58636 KB Output is correct
9 Correct 42 ms 59584 KB Output is correct
10 Correct 36 ms 59820 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 KB Output is correct
6 Correct 330 ms 116776 KB Output is correct
7 Correct 292 ms 58932 KB Output is correct
8 Correct 303 ms 117516 KB Output is correct
9 Correct 494 ms 116616 KB Output is correct
10 Correct 543 ms 118260 KB Output is correct
11 Correct 160 ms 58796 KB Output is correct
12 Correct 159 ms 59744 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 KB Output is correct
6 Correct 5 ms 5584 KB Output is correct
7 Correct 5 ms 8140 KB Output is correct
8 Correct 40 ms 58636 KB Output is correct
9 Correct 42 ms 59584 KB Output is correct
10 Correct 36 ms 59820 KB Output is correct
11 Correct 330 ms 116776 KB Output is correct
12 Correct 292 ms 58932 KB Output is correct
13 Correct 303 ms 117516 KB Output is correct
14 Correct 494 ms 116616 KB Output is correct
15 Correct 543 ms 118260 KB Output is correct
16 Correct 160 ms 58796 KB Output is correct
17 Correct 159 ms 59744 KB Output is correct
18 Runtime error 858 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -