oj.uz

Submission #1018187

# Submission time Handle Problem Language Result Execution time Memory
1018187 2024-07-09T16:02:47 Z dosts Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 854 ms 380176 KB 
#include "happiness.h"
//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
#define all(xx) xx.begin(),xx.end()
const int inf = 1e18;
int LIM;

struct Node {
	int sm=0,mn=inf;
	Node *l,*r;
} *root = new Node;

pii cmp(const pii& p1,const pii& p2) {
	if (p1.ff == inf) return p2;
	if (p2.ff == inf) return p1;
	return (p1.second < p2.second)?p1:p2;
}


void prop(Node* node,int l,int r,int p,int v) {
	if (l == r) {
		node->sm+= v*p;
		node->mn = node->sm ? -p+1 : inf;
		return;
	}
	int m = (l+r) >> 1;
	if (p <= m) {
		if (!node->l) node->l = new Node;
		prop(node->l,l,m,p,v);
		node->sm = node->l->sm+(node->r?node->r->sm:0);
		node->mn = node->l->mn;
		if (node->r) node->mn = min(node->mn,node->l->sm+node->r->mn);
	}
	else {
		if (!node->r) node->r = new Node;
		prop(node->r,m+1,r,p,v);
		node->sm = node->r->sm+(node->l?node->l->sm:0);
		node->mn = (node->l?node->l->sm:0)+node->r->mn;
		if (node->l) node->mn = min(node->mn,node->l->mn);	
	}
}


bool init(int32_t coinsCount, long long maxCoinSize, long long coins[]) {
	LIM = maxCoinSize;
	for (int i=0;i<coinsCount;i++) prop(root,1,LIM,coins[i],1);
	return root->mn >= 0;
}

bool is_happy(int32_t event, int32_t coinsCount, long long coins[]) {
	for (int i=0;i<coinsCount;i++) prop(root,1,LIM,coins[i],event);
	return root->mn>=0;
}

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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 1884 KB Output is correct
7 Correct 2 ms 1936 KB Output is correct
8 Correct 18 ms 14124 KB Output is correct
9 Correct 19 ms 14272 KB Output is correct
10 Correct 18 ms 13912 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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 209 ms 37456 KB Output is correct
7 Correct 194 ms 36948 KB Output is correct
8 Correct 226 ms 37460 KB Output is correct
9 Correct 330 ms 48792 KB Output is correct
10 Correct 358 ms 52724 KB Output is correct
11 Correct 116 ms 36944 KB Output is correct
12 Correct 123 ms 37200 KB Output is correct

Subtask #4
40.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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 1884 KB Output is correct
7 Correct 2 ms 1936 KB Output is correct
8 Correct 18 ms 14124 KB Output is correct
9 Correct 19 ms 14272 KB Output is correct
10 Correct 18 ms 13912 KB Output is correct
11 Correct 209 ms 37456 KB Output is correct
12 Correct 194 ms 36948 KB Output is correct
13 Correct 226 ms 37460 KB Output is correct
14 Correct 330 ms 48792 KB Output is correct
15 Correct 358 ms 52724 KB Output is correct
16 Correct 116 ms 36944 KB Output is correct
17 Correct 123 ms 37200 KB Output is correct
18 Correct 529 ms 225872 KB Output is correct
19 Correct 517 ms 234644 KB Output is correct
20 Correct 854 ms 380176 KB Output is correct
21 Correct 486 ms 199068 KB Output is correct
22 Correct 182 ms 39248 KB Output is correct
23 Correct 199 ms 39528 KB Output is correct
24 Correct 448 ms 216656 KB Output is correct