oj.uz

Submission #916960

# Submission time Handle Problem Language Result Execution time Memory
916960 2024-01-26T20:41:51 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+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;
	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 89 ms 433360 KB Output is correct
2 Correct 91 ms 433484 KB Output is correct
3 Correct 89 ms 433232 KB Output is correct
4 Correct 89 ms 433236 KB Output is correct
5 Correct 87 ms 433232 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 433360 KB Output is correct
2 Correct 91 ms 433484 KB Output is correct
3 Correct 89 ms 433232 KB Output is correct
4 Correct 89 ms 433236 KB Output is correct
5 Correct 87 ms 433232 KB Output is correct
6 Correct 87 ms 433148 KB Output is correct
7 Correct 89 ms 433240 KB Output is correct
8 Correct 104 ms 433232 KB Output is correct
9 Correct 102 ms 433232 KB Output is correct
10 Correct 100 ms 433204 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 433360 KB Output is correct
2 Correct 91 ms 433484 KB Output is correct
3 Correct 89 ms 433232 KB Output is correct
4 Correct 89 ms 433236 KB Output is correct
5 Correct 87 ms 433232 KB Output is correct
6 Correct 362 ms 434300 KB Output is correct
7 Correct 362 ms 434424 KB Output is correct
8 Correct 356 ms 434260 KB Output is correct
9 Correct 544 ms 434360 KB Output is correct
10 Correct 597 ms 434260 KB Output is correct
11 Correct 246 ms 433448 KB Output is correct
12 Correct 227 ms 433488 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 433360 KB Output is correct
2 Correct 91 ms 433484 KB Output is correct
3 Correct 89 ms 433232 KB Output is correct
4 Correct 89 ms 433236 KB Output is correct
5 Correct 87 ms 433232 KB Output is correct
6 Correct 87 ms 433148 KB Output is correct
7 Correct 89 ms 433240 KB Output is correct
8 Correct 104 ms 433232 KB Output is correct
9 Correct 102 ms 433232 KB Output is correct
10 Correct 100 ms 433204 KB Output is correct
11 Correct 362 ms 434300 KB Output is correct
12 Correct 362 ms 434424 KB Output is correct
13 Correct 356 ms 434260 KB Output is correct
14 Correct 544 ms 434360 KB Output is correct
15 Correct 597 ms 434260 KB Output is correct
16 Correct 246 ms 433448 KB Output is correct
17 Correct 227 ms 433488 KB Output is correct
18 Execution timed out 3015 ms 524288 KB Time limit exceeded
19 Halted 0 ms 0 KB -