제출 #467191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
467191		jli12345	Happiness (Balkan15_HAPPINESS)	C++14	60 / 100	1660 ms	408644 KiB

happiness

#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;
 
typedef long long ll;
 
struct Node{
    ll sum;
    int lson, rson;
 
    Node(){
        sum = 0;
        lson = rson = -1;
    }
} st[200100*64];
 
int nodecnt = 1;
 
void newnode(int node){
    if (st[node].lson == -1)
        st[node].lson = ++nodecnt;
    if (st[node].rson == -1)
        st[node].rson = ++nodecnt;
}
 
void U(int node, ll l, ll r, ll ind, ll val){
    if (l > ind || r < ind)
        return;
    if (l == r){
        st[node].sum += val;
        return;
    }
    newnode(node);
    ll mid = (l+r)/2;
    U(st[node].lson, l, mid, ind, val);
    U(st[node].rson, mid+1, r, ind, val);
    st[node].sum = st[st[node].lson].sum+st[st[node].rson].sum;
}
 
ll Q(int node, ll l, ll r, ll tl, ll tr){
    if (l > tr || r < tl)
        return 0;
    if (l >= tl && r <= tr)
        return st[node].sum;
    ll mid = (l+r)/2;
    newnode(node);
    return Q(st[node].lson, l, mid, tl, tr)+Q(st[node].rson, mid+1, r, tl, tr);
}
 
bool isValid(){
    ll curval = 2;
    ll sum = 0;
    while (curval <= min((ll)1e12, st[1].sum)){
        sum = Q(1, 1, 1e12, 1, curval-1);
        if (curval > sum+1){
            return false;
        }
        curval = sum+2;
       // cout << sum << "\n";
    }
    return true;
}
 
bool init(int coinsCount, long long maxCoinSize, long long coins[]){
    for (int i = 0; i < coinsCount; i++){
        U(1, 1, 1e12, coins[i], coins[i]);
    }
    return isValid();
}
 
bool is_happy(int event, int coinsCount, long long coins[]){
    for (int i = 0; i < coinsCount; i++){
        U(1, 1, 1e12, coins[i], event*coins[i]);
    }
    return isValid();
}

컴파일 시 표준 에러 (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: 0 / 40