제출 #1310941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310941		anandswaroop191	Happiness (Balkan15_HAPPINESS)	C++20	0 / 100	1 ms	572 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, ct, m, lz, s;
    Node *ln, *rn;
};

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

void ur(Node *n, int x, int d)
{
    // printf("in ur\n");
    auto &[l, r, ct, m, lz, s, ln, rn] = *n;
    // printf("unpacked %lld %lld %lld %lld %lld %lld %lld %lld\n", l, r, ct, m, lz, s, ln, rn);
    if (x >= r) return;
    if (x < l)
    {
        lz += x * d;
        if (ct) m += x * d;
        return;
    }
    assert(ln != nullptr);
    ur(ln, x, d);
    ur(rn, x, d);
    m = ninf;
    if (ln->ct) m = min(m, ln->m + lz);
    if (rn->ct) m = min(m, rn->m + lz);
}

void up(Node *n, int x, int d)
{
    // printf("in up\n");
    auto &[l, r, ct, m, lz, s, ln, rn] = *n;
    ct += d;
    s += x * d;
    if (l == r)
    {
        assert(l == x);
        if (ct) m = lz - x;
        else m = ninf;
        return;
    }
    
    int mid = (l + r) / 2;
    if (ln == nullptr)
    {
        assert(ct == d);
        ln = new Node {l, mid, 0, ninf, 0, 0, nullptr, nullptr},
        rn = new Node {mid + 1, r, 0, ninf, 0, 0, nullptr, nullptr};
    }
    if (x <= mid) up(ln, x, d);
    else up(rn, x, d);

    if (ct == 0)
    {
        assert(s == 0);
        assert(ln->lz == rn->lz);
        lz += ln->lz;
        m = ninf;
        fn(ln);
        fn(rn);
        ln = rn = nullptr;
    }
    else
    {
        m = ninf;
        if (ln->ct) m = min(m, ln->m + lz);
        if (rn->ct) m = min(m, rn->m + lz);
    }
}

void showtree(Node *n, int level)
{
    for (int i = 0; i < level; i ++) cout << ' ';
    if (n == nullptr)
    {
        printf("[null]\n");
        return;
    }
    auto &[l, r, ct, m, lz, s, ln, rn] = *n;
    printf("[%lld, %lld], ct=%lld, s=%lld, lz=%lld, m=%lld\n", l, r, ct, s, lz, m);
    showtree(ln, level+2);
    showtree(rn, level+2);
}

Node *st;
int nn, mm;

bool init(signed n, int m, int coins[])
{
    nn = n, mm = m;
    st = new Node {0, m, 0, ninf, 0, 0, nullptr, nullptr};
    sort(coins, coins + n);
    for (int i = 0; i < n; )
    {
        // printf("in loop\n");
        int v = coins[i++], ct = 1;
        while (i < n && coins[i] == v)
        {
            // printf("in while loop\n");
            i ++, ct ++;
        }
        up(st, v, ct);
        ur(st, v, ct);
        // printf("done updating\n");
    }
    // showtree(st, 0);
    // printf("exiting init\n");
    return st->m >= -1;
}

bool is_happy(signed ev, signed c, int coins[])
{
    sort(coins, coins + c);
    for (int i = 0; i < c; )
    {
        int v = coins[i++], ct = 1;
        while (i < nn && coins[i] == v) i ++, ct ++;
        if (ev == 1)
        {
            up(st, v, ct);
            ur(st, v, ct);
        }
        else
        {
            ur(st, v, -ct);
            up(st, v, -ct);
        }
    }
    // showtree(st, 0);
    return st->m >= -1;
}
    
// #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: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40