oj.uz

Submission #916977

# Submission time Handle Problem Language Result Execution time Memory
916977 2024-01-26T22:00:52 Z Nonoze Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 836 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=max(st[ st[root].left ].maxi, st[ st[root].right ].maxi - st[ st[root].left ].sum);
}

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 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 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 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 4800 KB Output is correct
7 Correct 5 ms 8908 KB Output is correct
8 Correct 45 ms 58808 KB Output is correct
9 Correct 38 ms 58548 KB Output is correct
10 Correct 39 ms 59836 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 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 323 ms 117964 KB Output is correct
7 Correct 332 ms 59764 KB Output is correct
8 Correct 299 ms 118364 KB Output is correct
9 Correct 558 ms 116956 KB Output is correct
10 Correct 567 ms 117584 KB Output is correct
11 Correct 160 ms 59684 KB Output is correct
12 Correct 161 ms 58284 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 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 4800 KB Output is correct
7 Correct 5 ms 8908 KB Output is correct
8 Correct 45 ms 58808 KB Output is correct
9 Correct 38 ms 58548 KB Output is correct
10 Correct 39 ms 59836 KB Output is correct
11 Correct 323 ms 117964 KB Output is correct
12 Correct 332 ms 59764 KB Output is correct
13 Correct 299 ms 118364 KB Output is correct
14 Correct 558 ms 116956 KB Output is correct
15 Correct 567 ms 117584 KB Output is correct
16 Correct 160 ms 59684 KB Output is correct
17 Correct 161 ms 58284 KB Output is correct
18 Runtime error 836 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -