제출 #1319773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319773		thuhienne	Happiness (Balkan15_HAPPINESS)	C++20	100 / 100	854 ms	237560 KiB

happiness

#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;

using ll = long long;

#define thuhien ""
#define re exit(0);

const int LOG = 40;

ll lim;
//s[i - 1] - a[i]
struct DynamicSegmentTree {
	struct node {
		int leftchild,rightchild;
		ll sum;
	} st[400009 * LOG];
	
	int stnode = 1;
	
	void createchild(int id) {
		if (st[id].leftchild) return;
		st[id].leftchild = ++stnode;
		st[id].rightchild = ++stnode;
	}
	
	void update(int id,long long l,long long r,long long pos,long long val) {
		if (l > pos || r < pos) return;
		if (l == r) {
			st[id].sum += val;
			return;
		}
		long long mid = (l + r) >> 1;
		
		createchild(id);
		
		update(st[id].leftchild,l,mid,pos,val);
		update(st[id].rightchild,mid+1,r,pos,val);
		
		st[id].sum = st[st[id].leftchild].sum + st[st[id].rightchild].sum;
		
	}
	
	ll get(int id,long long l,long long r,long long u,long long v) {
		if (l > v || r < u || st[id].sum == 0) return 0;
		if (l >= u && r <= v) return st[id].sum;;
		
		long long mid = (l + r) >> 1;
		
		createchild(id);
		
		return get(st[id].leftchild,l,mid,u,v) + get(st[id].rightchild,mid + 1,r,u,v);
	}
	
	
} SegTree;

bool check() {
	ll currsum = 0,allsum = SegTree.get(1,1,lim,1,lim);
	while (currsum < allsum) {
		ll nextsum = SegTree.get(1,1,lim,1,currsum + 1);
		if (nextsum <= currsum) return 0;
		currsum = nextsum;
	}
	return 1;
}

bool init(int cnt,ll maxsize,ll tmp[]) {
	lim = maxsize + 3;
	
	for (int i = 0;i < cnt;i++) {
		SegTree.update(1,1,lim,tmp[i],tmp[i]);
	}
	
	return check();
}
bool is_happy(int type,int cnt,ll tmp[]) {
	for (int i = 0;i < cnt;i++) {
		SegTree.update(1,1,lim,tmp[i],tmp[i] * type);
	}
	
	return check();
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40