Submission #1311002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311002		anandswaroop191	Happiness (Balkan15_HAPPINESS)	C++20	100 / 100	1368 ms	372280 KiB

happiness

#include <bits/stdc++.h>
#include "happiness.h"

using namespace std;
#define int long long
using pii = pair<int, int>;
#define read(a) for (auto &x : a) cin >> x
#define V vector
#define show(a) for (auto x : a) cout << x << " "; cout << endl;
const int ninf = numeric_limits<int>::max();

struct Node
{
    int l, r, s;
    Node *ln, *rn;
};

void fn(Node *n)
{
    if (n == nullptr) return;
    fn(n->ln);
    fn(n->rn);
    delete n;
}

void u(Node *n, int x, int ct)
{
    auto &[l, r, s, ln, rn] = *n;
    s += x * ct;
    if (l == r) return;
    int m = (l + r) / 2;
    if (x <= m)
    {
        if (!ln) ln = new Node {l, m, 0, nullptr, nullptr};
        u(ln, x, ct);
    }
    else
    {
        if (!rn) rn = new Node {m + 1, r, 0, nullptr, nullptr};
        u(rn, x, ct);
    }
}

void showtree(Node *n, int lev)
{
    for (int i = 0; i < lev; i ++) cout << ' ';
    if (!n)
    {
        printf("[null]\n");
        return;
    }
    printf("[%lld, %lld], s=%lld\n", n->l, n->r, n->s);
    showtree(n->ln, lev + 2);
    showtree(n->rn, lev + 2);
}

int qu(Node *n, int ql, int qr)
{
    if (!n) return 0;

    auto &[l, r, s, ln, rn] = *n;
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return s;
    return qu(ln, ql, qr) + qu(rn, ql, qr);
}

Node *st;

bool check()
{
    int cur = 1, tot = st->s;
    while (cur < tot)
    {
        int s = qu(st, 1, cur);
        if (s < cur) return false;
        cur = s + 1;
    }
    return true;
}

bool init(signed n, int m, int coins[])
{
    st = new Node {1, m, 0, nullptr, nullptr};
    for (int i = 0; i < n; i ++)
    {
        u(st, coins[i], 1);
    }
    // showtree(st, 0);
    return check();
}

bool is_happy(signed ev, signed c, int coins[])
{
    for (int i = 0; i < c; i ++)
    {
        u(st, coins[i], ev);
    }
    // showtree(st, 0);
    return check();
}
    
// #define NMAX 200000
// #define QMAX 100000

// static signed N, Q;
// static long long M;
// static long long coins[NMAX], A[5];

// signed main()
// {
// 	signed i, d;
// 	long long max_code;

// 	scanf("%d%lld", &N, &M);
// 	for (i = 0; i < N; ++i) {
// 		scanf("%lld", &coins[i]);
// 	}
// 	if (init(N, M, coins))printf("1\n");
// 	else printf("0\n");
// 	scanf("%d", &Q);
// 	for (i = 0; i < Q; ++i) {
// 		signed ck, c;
// 		scanf("%d%d", &ck, &c);
// 		for (int j = 0; j < c; j++) {
// 			scanf("%lld", &A[j]);
// 		}
// 		if (is_happy(ck, c, A))printf("1\n");
// 		else printf("0\n");
// 	}

// 	return 0;
// }

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