oj.uz

Submission #916973

# Submission time Handle Problem Language Result Execution time Memory
916973 2024-01-26T21:39:36 Z Nonoze Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 524288 KB 
#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long


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

node st[123456*64];
int cnt=1;

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 = cnt++;
		st[ st[root].left ].l=left, st[ st[root].left ].r=mid;
	}
	if (st[root].right==-1) {
		st[root].right = cnt++;
		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[]) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	mx=mxx;
	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 72 ms 433492 KB Output is correct
2 Correct 72 ms 433540 KB Output is correct
3 Correct 72 ms 433512 KB Output is correct
4 Correct 68 ms 433476 KB Output is correct
5 Correct 70 ms 433488 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 433492 KB Output is correct
2 Correct 72 ms 433540 KB Output is correct
3 Correct 72 ms 433512 KB Output is correct
4 Correct 68 ms 433476 KB Output is correct
5 Correct 70 ms 433488 KB Output is correct
6 Correct 70 ms 433568 KB Output is correct
7 Correct 70 ms 433356 KB Output is correct
8 Correct 84 ms 433492 KB Output is correct
9 Correct 84 ms 433600 KB Output is correct
10 Correct 82 ms 433584 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 433492 KB Output is correct
2 Correct 72 ms 433540 KB Output is correct
3 Correct 72 ms 433512 KB Output is correct
4 Correct 68 ms 433476 KB Output is correct
5 Correct 70 ms 433488 KB Output is correct
6 Correct 376 ms 434684 KB Output is correct
7 Correct 334 ms 434256 KB Output is correct
8 Correct 347 ms 434512 KB Output is correct
9 Correct 524 ms 434360 KB Output is correct
10 Correct 550 ms 434408 KB Output is correct
11 Correct 215 ms 433688 KB Output is correct
12 Correct 217 ms 433740 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 433492 KB Output is correct
2 Correct 72 ms 433540 KB Output is correct
3 Correct 72 ms 433512 KB Output is correct
4 Correct 68 ms 433476 KB Output is correct
5 Correct 70 ms 433488 KB Output is correct
6 Correct 70 ms 433568 KB Output is correct
7 Correct 70 ms 433356 KB Output is correct
8 Correct 84 ms 433492 KB Output is correct
9 Correct 84 ms 433600 KB Output is correct
10 Correct 82 ms 433584 KB Output is correct
11 Correct 376 ms 434684 KB Output is correct
12 Correct 334 ms 434256 KB Output is correct
13 Correct 347 ms 434512 KB Output is correct
14 Correct 524 ms 434360 KB Output is correct
15 Correct 550 ms 434408 KB Output is correct
16 Correct 215 ms 433688 KB Output is correct
17 Correct 217 ms 433740 KB Output is correct
18 Execution timed out 2907 ms 524288 KB Time limit exceeded
19 Halted 0 ms 0 KB -