Submission #284037

#	Time	Username	Problem	Language	Result	Execution time	Memory
284037		NaimSS	Happiness (Balkan15_HAPPINESS)	C++14	0 / 100	1 ms	384 KiB

happiness

#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;

const ll inf = 1e16;
const ll MAX = (1e12) + 1;
struct node{
	node *l,*r;
	ll mx;
	ll lazy;
	ll sum;
	node(){
		l = r = NULL;
	 	sum = lazy = 0;	
		mx = 0;
	}

	void push(ll i,ll j){
		if(lazy == 0)return;
		mx+=lazy;
		if(i == j){
			lazy = 0;
			return;
		}
		ll mid = (i+j)/2;
		if(l == NULL)l = new node();
		if(r == NULL)r = new node();

		l->lazy +=lazy;
		r->lazy +=lazy;

		lazy = 0;
	}
	void update(ll i,ll j,ll a,ll b,ll val){
		push(i,j);
		if(i > b || j < a)return;
		if(a<=i and j<=b){
			lazy+=val;
			push(i,j);
			return;
		}

		ll mid = (i+j)/2;
		if(!(i>b || mid < a)){
			if(l == NULL) l = new node();
			l->update(i,mid,a,b,val);
		}
		if(!(mid+1>b || j < a)){
			if(r == NULL)r = new node();
			r->update(mid+1,j,a,b,val);
		}

		
		mx = max(l!=NULL ? l->mx : -inf,r!=NULL ? r->mx : - inf); 
	}
	ll query(ll i,ll j,ll a,ll b){
		push(i,j);
		if(a<=i and j<=b)return mx;
		ll mid = (i+j)/2;
		ll op1 = -inf,op2 = inf;
		if(!(i>b || mid < a) and l!=NULL){
			op1=l->query(i,mid,a,b);
		}
		if(!(mid+1>b || j<a) and r!=NULL){
			op2 = r->query(mid+1,j,a,b);
		}
		return max(op1,op2);
	}

};

node* tree;
static int N;
static int cnt1 = 0;
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	tree = new node();
	tree->update(1,MAX,1,MAX,-1);
	if(MAX <= maxCoinSize)assert(false);

	N = coinsCount;
	for(int i=0;i<N;i++){
		ll val = coins[i];
		if(val == 1){
			cnt1++;
		}
		tree->update(1,MAX,val+1,MAX,-val);
		tree->update(1,MAX,val,val,+val);
	}
	ll mx = tree->query(1,MAX,2,MAX);
	if(N == 0)return true;
	if( mx <=0 and cnt1 > 0 )return true;
	return false;
}
bool is_happy(int event, int coinsCount, long long coins[]) {
	
	N+=coinsCount*event;
	for(int i=0;i<coinsCount;i++){
			ll val = coins[i];
			ll sla = val;
			if(event == -1)sla = -sla;
			if(val == 1){
				cnt1+=event;
			}
			tree->update(1,MAX,val+1,MAX,-sla);
			tree->update(1,MAX,val,val,+sla);
	}
	

	ll mx = tree->query(1,MAX,2,MAX);
	if(N == 0)return true;
	if( mx <=0 and cnt1 > 0 )return true;
	return false;	
}

Compilation message (stderr)

happiness.cpp: In member function 'void node::push(ll, ll)':
happiness.cpp:41:6: warning: unused variable 'mid' [-Wunused-variable]
   41 |   ll mid = (i+j)/2;
      |      ^~~
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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40