Submission #1319768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319768		thuhienne	Happiness (Balkan15_HAPPINESS)	C++20	0 / 100	0 ms	332 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,minval,lazy;
	} st[400009 * LOG];
	int stnode;
	
	void createchild(int id) {
		if (st[id].leftchild) return;
		
		st[id].leftchild = ++stnode;
		st[id].rightchild = ++stnode;
	}
	
	void push_down(int id) {
		if (st[id].lazy == 0) return;
		
		st[st[id].leftchild].minval += st[id].lazy;
		st[st[id].rightchild].minval += st[id].lazy;
		
		st[st[id].leftchild].lazy += st[id].lazy;
		st[st[id].rightchild].lazy += st[id].lazy;
		
		st[id].lazy = 0;
	}
	
	void refine(int id) {
		st[id].minval = min(st[st[id].leftchild].minval,st[st[id].rightchild].minval);
		st[id].sum = st[st[id].leftchild].sum + st[st[id].rightchild].sum;
	}
	
	ll getsum(int id,ll l,ll r,int u,int v) {
		if (l > v || r < u || st[id].sum == 0) return 0;
		if (l >= u && r <= v) return st[id].sum;
		
		ll mid = (l + r) >> 1;
		
		createchild(id);
		push_down(id);
		
		return getsum(st[id].leftchild,l,mid,u,v) + getsum(st[id].rightchild,mid + 1,r,u,v);
		
	}
	
	void change(int id,ll l,ll r,ll pos,int type) {
		if (l == r) {
			if (type == -1) {
			
				st[id].sum -= pos;
				if (st[id].sum == 0) st[id].minval = 0;
			
			} else {
				
				if (st[id].sum == 0) st[id].minval = getsum(1,1,lim,1,pos - 1) + 1 - pos;
				st[id].sum += pos;
			
			}
			
			return;
		}
		
		ll mid = (l + r) >> 1;
		
		createchild(id);
		push_down(id);
		
		if (pos <= mid) change(st[id].leftchild,l,mid,pos,type);
		else change(st[id].rightchild,mid + 1,r,pos,type);
		
		refine(id);
	}
	
	void update(int id,ll l,ll r,ll u,ll v,ll val) {
		if (l > v || r < u) return;
		if (l >= u && r <= v) {
			st[id].minval += val;
			st[id].lazy += val;
			return;
		}
		
		ll mid = (l + r) >> 1;
		
		createchild(id);
		push_down(id);
		
		update(st[id].leftchild,l,mid,u,v,val);
		update(st[id].rightchild,mid + 1,r,u,v,val);
		
		refine(id);
		
	}
	
	
	
} SegTree;

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

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