제출 #538360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
538360		fcw	Happiness (Balkan15_HAPPINESS)	C++17	100 / 100	1850 ms	395380 KiB

happiness

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

using lint = long long;
lint LIM = 1e12 + 10;

struct node{
	lint sum, lz;
	int l, r;
	node(): sum(0), lz(0), l(0), r(0) {}
};

vector<node>seg;

int create(){
	seg.push_back(node());
	return seg.size() - 1;
}

void push(int v, lint l, lint r){
}

void update(int v, lint l, lint r, lint a, lint b, lint val){
	if(b < l || r < a) return;
	push(v, l, r);
	if(a <= l && r <= b){
		seg[v].sum += val;
		push(v, l, r);
		return;
	}
	lint m = (l + r) >> 1;
	if(!seg[v].l){
		int aux = create();
		seg[v].l = aux;
	}
	if(!seg[v].r){
		int aux = create();
		seg[v].r = aux;
	}
	update(seg[v].l, l, m, a, b, val);
	update(seg[v].r, m+1, r, a, b, val);
	push(seg[v].l, l, m);
	push(seg[v].r, m+1, r);
	seg[v].sum = seg[seg[v].l].sum + seg[seg[v].r].sum;
}

lint query(int v, lint l, lint r, lint a, lint b){
	if(b < l || r < a) return 0;
	if(v == 0) return 0;
	push(v, l, r);
	if(a <= l && r <= b){
		return seg[v].sum;
	}
	lint m = (l + r) >> 1;
	return query(seg[v].l, l, m, a, b) + query(seg[v].r, m+1, r, a, b);
}

bool check(){
	lint cur = 0, sum = seg[1].sum;
	while(cur < sum){
		lint cnt = query(1, 1, LIM, 1, cur);
		if(cnt < cur) return 0;
		cur = cnt + 1;
	}
	return 1;
}

bool init(int coinsCount, lint maxCoinSize, lint coins[]) {
	create();
	create();
	for(int i=0;i<coinsCount;i++){
		update(1, 1, LIM, coins[i], coins[i], coins[i]);
	}
	return check();
}

bool is_happy(int event, int coinsCount, lint coins[]) {
	for(int i=0;i<coinsCount;i++){
		update(1, 1, LIM, coins[i], coins[i], coins[i] * event);
	}
	return check();
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40