Submission #383121

#	Time	Username	Problem	Language	Result	Execution time	Memory
383121		JerryLiu06	Happiness (Balkan15_HAPPINESS)	C++11	0 / 100	128 ms	251116 KiB

happiness

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Node { ll sum = 0, tl, tr; int l = -1, r = -1; };

int N, M, Q, timer = 2; Node tree[8000000];

void pushdown(int x) { ll mid = (tree[x].tl + tree[x].tr) / 2;
    if (tree[x].l == -1) { tree[x].l = timer++; tree[tree[x].l].tl = tree[x].tl; tree[tree[x].l].tr = mid; }
    if (tree[x].r == -1) { tree[x].r = timer++; tree[tree[x].r].tl = mid + 1; tree[tree[x].r].tr = tree[x].tr; }
}
void update(int x, ll pos, ll val) { ll mid = (tree[x].tl + tree[x].tr) / 2;
    if (tree[x].tl > pos || tree[x].tr < pos) return ; if (tree[x].tl == tree[x].tr) { tree[x].sum = val; return ; }

    pushdown(x); update(tree[x].l, pos, val); update(tree[x].r, pos, val); tree[x].sum = tree[tree[x].l].sum + tree[tree[x].r].sum;
}
ll query(int x, int l, int r) { ll mid = (tree[x].tl + tree[x].tr) / 2;
    if (tree[x].tl > r || tree[x].tr < l) return 0; if (l <= tree[x].tl && tree[x].tr <= r) return tree[x].sum;

    pushdown(x); return query(tree[x].l, l, r) + query(tree[x].r, l, r);
}
bool valid() {
    ll CUR = 1; ll TOT = query(1, 1, M);

    while (CUR <= TOT) { ll PREF = query(1, 1, CUR);

        if (CUR <= PREF) CUR = PREF + 1; else return false;
    }
    return true;
}
bool init(int countCoins, ll maxCoinSize, ll coins[]) { 
    tree[1].tl = 1; tree[1].tr = maxCoinSize;

    for (int i = 0; i < countCoins; i++) update(1, coins[i], coins[i]);

    return valid();
}
bool is_happy(int event, int countCoins, ll coins[]) {
    if (event == 1) for (int i = 0; i < countCoins; i++) update(1, coins[i], coins[i]);
    if (event == -1) for (int i = 0; i < countCoins; i++) update(1, coins[i], 0);

    return valid();
}

// int main() {   
//     ios_base::sync_with_stdio(false); cin.tie(0);

//     cin >> N >> M; tree[1].tl = 1; tree[1].tr = M;
    
//     for (int i = 0; i < N; i++) { ll C; cin >> C; update(1, C, C); }

//     cin >> Q; for (int i = 0; i <= Q; i++) {
    
//         if (!query(1, 1, 1)) { cout << "false" << "\n"; continue; }
        
//         bool FIN = true; ll CUR = 2; ll TOT = query(1, 1, M);

//         while (CUR <= TOT) { ll PREF = query(1, 1, CUR) + 1;

//             if (CUR <= PREF) CUR += PREF; else { FIN = false; break; }
//         }
//         cout << FIN << "\n";
        
//         if (i < Q) {
        
//             int T, X; cin >> T >> X;

//             if (T == 1) { for (int i = 0; i < X; i++) { ll A; cin >> A; update(1, A, A); } }
//             if (T == -1) { for (int i = 0; i < X; i++) { ll A; cin >> A; update(1, A, 0); } }
//         }
//     }
// }

Compilation message (stderr)

happiness.cpp: In function 'void update(int, ll, ll)':
happiness.cpp:16:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   16 |     if (tree[x].tl > pos || tree[x].tr < pos) return ; if (tree[x].tl == tree[x].tr) { tree[x].sum = val; return ; }
      |     ^~
happiness.cpp:16:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   16 |     if (tree[x].tl > pos || tree[x].tr < pos) return ; if (tree[x].tl == tree[x].tr) { tree[x].sum = val; return ; }
      |                                                        ^~
happiness.cpp:15:41: warning: unused variable 'mid' [-Wunused-variable]
   15 | void update(int x, ll pos, ll val) { ll mid = (tree[x].tl + tree[x].tr) / 2;
      |                                         ^~~
happiness.cpp: In function 'll query(int, int, int)':
happiness.cpp:21:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   21 |     if (tree[x].tl > r || tree[x].tr < l) return 0; if (l <= tree[x].tl && tree[x].tr <= r) return tree[x].sum;
      |     ^~
happiness.cpp:21:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   21 |     if (tree[x].tl > r || tree[x].tr < l) return 0; if (l <= tree[x].tl && tree[x].tr <= r) return tree[x].sum;
      |                                                     ^~
happiness.cpp:20:36: warning: unused variable 'mid' [-Wunused-variable]
   20 | ll query(int x, int l, int r) { ll mid = (tree[x].tl + tree[x].tr) / 2;
      |                                    ^~~
grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~

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