oj.uz

Submission #916955

# Submission time Handle Problem Language Result Execution time Memory
916955 2024-01-26T20:35:42 Z Nonoze Happiness (Balkan15_HAPPINESS) C++17
30 / 100
 2000 ms 6548 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;
multiset<int> act;

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), act.insert(coins[i]);
	update(0, 1, mx+1, *act.begin(), *act.begin(), -1);
	int ans=st[0].maxi;
	update(0, 1, mx+1, *act.begin(), *act.begin(), 1);
	return ans<=(1+*act.begin());
}
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);
		if (event==1) act.insert(coins[i]);
		else act.erase(act.find(coins[i]));
	}
	update(0, 1, mx+1, *act.begin(), *act.begin(), -1);
	int ans=st[0].maxi;
	update(0, 1, mx+1, *act.begin(), *act.begin(), 1);
	return ans<=(1+*act.begin());
}*/


multiset<int> multi;

bool query() {
	int sumact=1;
	for (auto u=multi.begin(); u!=multi.end(); u++) {
		if (*u>sumact) return false;
		sumact+=*u;
	}
	return true;
}

bool init(signed n, long long mxx, long long coins[]) {
	for (int i=0; i<n; i++) multi.insert(coins[i]);
	return query();

}
bool is_happy(signed event, signed n, long long coins[]) {
	for (int i=0; i<n; i++) {
		if (event==1) multi.insert(coins[i]);
		else multi.erase(multi.find(coins[i]));
	}
	return query();
}

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 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 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 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 85 ms 964 KB Output is correct
9 Correct 85 ms 1116 KB Output is correct
10 Correct 89 ms 1368 KB Output is correct

Subtask #3
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 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Execution timed out 2025 ms 6548 KB Time limit exceeded
7 Halted 0 ms 0 KB -

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 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 85 ms 964 KB Output is correct
9 Correct 85 ms 1116 KB Output is correct
10 Correct 89 ms 1368 KB Output is correct
11 Execution timed out 2025 ms 6548 KB Time limit exceeded
12 Halted 0 ms 0 KB -