제출 #1312420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312420		a5a7	Happiness (Balkan15_HAPPINESS)	C++20	100 / 100	1633 ms	372148 KiB

happiness

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

struct SparseNode{
    SparseNode *left = NULL, *right = NULL;
    ll sum = 0;
    bool lazy = false;
    SparseNode() {};
} *root = new SparseNode;

void add(SparseNode *curr, ll curr_left, ll curr_right, ll query, ll val){
    if (curr_left > query || curr_right < query) return;
    curr->sum += val;
    if (curr_left == curr_right) return;
    ll m = (curr_left+curr_right)/2;
    if (query <= m){
        if (!curr->left) curr->left = new SparseNode; 
        add(curr->left, curr_left, m, query, val);
    }else{
        if (!curr->right) curr->right = new SparseNode;
        add(curr->right, m+1, curr_right, query, val);
    }
}

ll range(SparseNode *curr, ll curr_left, ll curr_right, ll left, ll right){
    if (!curr || curr_left > right || curr_right < left) return 0;
    if (curr_left >= left && right >= curr_right) return curr->sum;
    ll m = (curr_left+curr_right)/2;
    return range(curr->left, curr_left, m, left, right)+range(curr->right, m+1, curr_right, left, right);
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    ll l = 0, r = 1e12;
    for (int i = 0; i < coinsCount; i++){
        add(root, l, r, coins[i], coins[i]);
    }
    ll currSum = 0;
    bool works = true;
    while (works){
        ll nextSum = range(root, l, r, 1, currSum+1);
        if (nextSum == currSum){
            works = false;
        }
        currSum = nextSum;
    }
	return currSum >= range(root, l, r, l, r);
}

bool is_happy(int event, int coinsCount, long long coins[]) {
    ll l = 0, r = 1e12;
	if (event == -1){
        for (int i = 0; i < coinsCount; i++){
            add(root, l, r, coins[i], -coins[i]);
        }
    }else{
        for (int i = 0; i < coinsCount; i++){
            add(root, l, r, coins[i], coins[i]);
        }
    }
    ll currSum = 0;
    bool works = true;
    while (works){
        ll nextSum = range(root, l, r, 1, currSum+1);
        if (nextSum == currSum){
            works = false;
        }
        currSum = nextSum;
    }
	return currSum >= range(root, l, r, l, r);
}

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