oj.uz

Submission #594540

# Submission time Handle Problem Language Result Execution time Memory
594540 2022-07-12T16:15:28 Z Do_you_copy Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1561 ms 481832 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <ll, ll>;
using pil = pair <ll, ll>;
using pli = pair <ll, ll>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const ll maxN = 1e5 + 1;
const ll inf = 1e12;
ll n;
ll a[maxN];
ll node_cnt = 1;

struct TNode{
    TNode *lp, *rp;
    ll val;
    TNode() : lp(nullptr), rp(nullptr), val(0){}
    void update(TNode* id, ll i, ll v, ll l = 1, ll r = inf){
        if (i < l || i > r) return;
        id->val += v;
        if (l == r){
            return;
        }
        id->create_node();
        ll mid = (l + r) / 2;
        update(id->lp, i, v, l, mid);
        update(id->rp, i, v, mid + 1, r);
    }
    void create_node(){
        if (!lp) lp = new TNode();
        if (!rp) rp = new TNode();
    }
    ll get(TNode* id, ll i, ll j, ll l = 1, ll r = inf){
        if (r < i || l > j) return 0;
        if (i <= l && r <= j) return id->val;
        ll mid = (l + r) / 2;
        ll ret = 0;
        if (id->lp) ret += get(id->lp, i, j, l, mid);
        if (id->rp) ret += get(id->rp, i, j, mid + 1, r);
        return ret;
    }
};

TNode* st;

bool check(){
    ll tem = 1, last = st->val;
    while (tem < last){
        ll t = st->get(st, 1, tem);
        if (t < tem) return 0;
        tem = t + 1;
    }
    return 1;
}

bool init(int N, ll M, ll a[]){
    n = N;
    st = new TNode();
    for (ll i = 0; i < n; ++i) st->update(st, a[i], a[i]);
    return check();
}

bool is_happy(int t, int K, ll a[]){
    for (ll i = 0; i < K; ++i) st->update(st, a[i], a[i] * t);
    return check();
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 2260 KB Output is correct
7 Correct 4 ms 2388 KB Output is correct
8 Correct 35 ms 17880 KB Output is correct
9 Correct 33 ms 18104 KB Output is correct
10 Correct 29 ms 17504 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 549 ms 34156 KB Output is correct
7 Correct 516 ms 37124 KB Output is correct
8 Correct 625 ms 37428 KB Output is correct
9 Correct 737 ms 46588 KB Output is correct
10 Correct 721 ms 49524 KB Output is correct
11 Correct 245 ms 26040 KB Output is correct
12 Correct 225 ms 26156 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 2260 KB Output is correct
7 Correct 4 ms 2388 KB Output is correct
8 Correct 35 ms 17880 KB Output is correct
9 Correct 33 ms 18104 KB Output is correct
10 Correct 29 ms 17504 KB Output is correct
11 Correct 549 ms 34156 KB Output is correct
12 Correct 516 ms 37124 KB Output is correct
13 Correct 625 ms 37428 KB Output is correct
14 Correct 737 ms 46588 KB Output is correct
15 Correct 721 ms 49524 KB Output is correct
16 Correct 245 ms 26040 KB Output is correct
17 Correct 225 ms 26156 KB Output is correct
18 Correct 1057 ms 286280 KB Output is correct
19 Correct 1134 ms 297672 KB Output is correct
20 Correct 1561 ms 481832 KB Output is correct
21 Correct 849 ms 252076 KB Output is correct
22 Correct 302 ms 28108 KB Output is correct
23 Correct 238 ms 28620 KB Output is correct
24 Correct 1086 ms 274224 KB Output is correct