oj.uz

Submission #916957

# Submission time Handle Problem Language Result Execution time Memory
916957 2024-01-26T20:39:21 Z Nonoze Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 855 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+1<=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);
	return;
}

int mx;

bool init(signed n, long long mxx, long long coins[]) {
	mx=mxx+100;
	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 84 ms 433364 KB Output is correct
2 Correct 86 ms 433344 KB Output is correct
3 Correct 85 ms 433240 KB Output is correct
4 Correct 85 ms 433236 KB Output is correct
5 Correct 86 ms 433416 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 433364 KB Output is correct
2 Correct 86 ms 433344 KB Output is correct
3 Correct 85 ms 433240 KB Output is correct
4 Correct 85 ms 433236 KB Output is correct
5 Correct 86 ms 433416 KB Output is correct
6 Correct 85 ms 433236 KB Output is correct
7 Correct 89 ms 433232 KB Output is correct
8 Correct 101 ms 433236 KB Output is correct
9 Correct 101 ms 433232 KB Output is correct
10 Correct 99 ms 433236 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 433364 KB Output is correct
2 Correct 86 ms 433344 KB Output is correct
3 Correct 85 ms 433240 KB Output is correct
4 Correct 85 ms 433236 KB Output is correct
5 Correct 86 ms 433416 KB Output is correct
6 Correct 350 ms 434256 KB Output is correct
7 Correct 363 ms 434432 KB Output is correct
8 Correct 382 ms 434260 KB Output is correct
9 Correct 526 ms 434188 KB Output is correct
10 Correct 635 ms 434272 KB Output is correct
11 Correct 235 ms 433440 KB Output is correct
12 Correct 245 ms 433488 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 433364 KB Output is correct
2 Correct 86 ms 433344 KB Output is correct
3 Correct 85 ms 433240 KB Output is correct
4 Correct 85 ms 433236 KB Output is correct
5 Correct 86 ms 433416 KB Output is correct
6 Correct 85 ms 433236 KB Output is correct
7 Correct 89 ms 433232 KB Output is correct
8 Correct 101 ms 433236 KB Output is correct
9 Correct 101 ms 433232 KB Output is correct
10 Correct 99 ms 433236 KB Output is correct
11 Correct 350 ms 434256 KB Output is correct
12 Correct 363 ms 434432 KB Output is correct
13 Correct 382 ms 434260 KB Output is correct
14 Correct 526 ms 434188 KB Output is correct
15 Correct 635 ms 434272 KB Output is correct
16 Correct 235 ms 433440 KB Output is correct
17 Correct 245 ms 433488 KB Output is correct
18 Runtime error 855 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -