oj.uz

Submission #1018164

# Submission time Handle Problem Language Result Execution time Memory
1018164 2024-07-09T15:33:33 Z dosts Happiness (Balkan15_HAPPINESS) C++17
0 / 100
 0 ms 348 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 lazy = 0;
	pii val = {inf,0};
	Node *l=nullptr, *r=nullptr;
	void push() {
		if (!lazy) return;
		val.ss+=lazy;
		if (!l) l = new Node;
		if (!r) r = new Node;
		l->lazy+=lazy;
		r->lazy+=lazy;
		lazy = 0;
	}
} *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;
}

pii vall(const Node* node){
	return (!node)? pii{inf,inf} : node->val;
}

void insert(Node* node,int l,int r,int p) {
	node->push();
	if (l == r) {
		if (node->val.ff == inf) {
			node->val.ff = 1;
			node->val.ss -= 2*p;
		}
		else node->val.ff++;
		return;
	}
	int m = (l+r) >> 1;
	if (p <= m) {
		if (!node->l) node->l = new Node;
		insert(node->l,l,m,p);
	}
	else{
		if (!node->r) node->r = new Node;
		insert(node->r,m+1,r,p);
	}
	node->val = cmp(vall(node->l),vall(node->r));
}



void remove(Node* node,int l,int r,int p) {
	node->push();
	if (l == r) {
		if (node->val.ff == 1) {
			node->val.ff = inf;
			node->val.ss+=2*p;
		}
		else node->val.ff--;
		return;
	}
	int m = (l+r) >> 1;
	if (p <= m) {
		if (!node->l) node->l = new Node;
		remove(node->l,l,m,p);
	}
	else{
		if (!node->r) node->r = new Node;
		remove(node->r,m+1,r,p);
	}
	node->val = cmp(vall(node->l),vall(node->r));
}

void prop(Node* node,int l,int r,int L,int R,int v) {
	node->push();
	if (l >= L && r <= R) {
		node->lazy+=v;
		node->push();
		return;
	}
	int m = (l+r) >> 1;
	if (!node->l) node->l = new Node;
	if (!node->r) node->r = new Node;
	if (m >= L) prop(node->l,l,m,L,R,v);
	if (m+1<=R) prop(node->r,m+1,r,L,R,v);
	node->l->push(),node->r->push();
	node->val = cmp(node->l->val,node->r->val);
}


pii query(Node* node,int l,int r,int p) {
	node->push();
	if (l == r) return node->val;
	int m = (l+r) >> 1;
	if (!node->l) node->l = new Node;
	if (!node->r) node->r = new Node;
	if (p <= m) return query(node->l,l,m,p);
	else return query(node->r,m+1,r,p);
}
bool init(int32_t coinsCount, long long maxCoinSize, long long coins[]) {
	LIM = maxCoinSize;
	for (int i=0;i<coinsCount;i++) {
		insert(root,1,LIM,coins[i]);
		prop(root,1,LIM,coins[i],LIM,coins[i]);
	}
	root->push();
	return (root->val.ff==inf || root->val.ss >= -1);
}

bool is_happy(int32_t event, int32_t coinsCount, long long coins[]) {
	if (event == -1) {
		for (int i=0;i<coinsCount;i++) {
			remove(root,1,LIM,coins[i]);
			prop(root,1,LIM,coins[i],LIM,-coins[i]);
		}
	}
	else {
		for (int i=0;i<coinsCount;i++) {
			insert(root,1,LIM,coins[i]);
			prop(root,1,LIM,coins[i],LIM,coins[i]);
		}
	}
	root->push();
	return (root->val.ff==inf || root->val.ss >= -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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -