oj.uz

Submission #899681

# Submission time Handle Problem Language Result Execution time Memory
899681 2024-01-06T20:57:58 Z trMatherz Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 994 ms 380576 KB 
//#include <iostream> //cin, cout
#include "happiness.h"
/*
#include <fstream>
std::ifstream cin ("ex.in");
std::ofstream cout ("ex.out");
*/




// includes
#include <cmath> 
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>



//usings 
using namespace std;
using namespace __gnu_pbds;


// misc
#define ll long long
#define pb push_back
#define pq priority_queue
#define ub upper_bound
#define lb lower_bound
template<typename T, typename U> bool emin(T &a, const U &b){ return b < a ? a = b, true : false; }
template<typename T, typename U> bool emax(T &a, const U &b){ return b > a ? a = b, true : false; }
typedef uint64_t hash_t;

// vectors
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vpii vector<pair<int, int>>
#define vvpii vector<vector<pair<int, int>>>
#define vppipi vector<pair<int, pair<int, int>>>
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>
#define vpll vector<pair<ll, ll>>
#define vb vector<bool>
#define vvb vector<vb>
#define vs vector<string>
#define sz(x) (int)x.size()
#define rz(x,y) x.resize(y)
#define all(x) x.begin(), x.end()


// pairs
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define f first
#define s second

// sets
#define si set<int>
#define sl set<ll>
#define ss set<string>
#define in insert
template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// maps
#define mii map<int, int>
#define mll map<ll, ll>

// loops
#define FR(x, z, y) for (int x = z; x < y; x++)
#define FRe(x, z, y) FR(x, z, y + 1)
#define F(x, y) FR(x, 0, y)
#define Fe(x, y) F(x, y + 1)
#define A(x, y) for(auto &x : y)

struct Node {
    ll l, r, v = 0;
    Node *lc = nullptr, *rc = nullptr;
    Node(ll tl, ll tr) : l(tl), r(tr) {}

   

    void put(ll x, ll z){
        v += z;
        if(l != r){
            ll m = (l + r) / 2;
            if(x > m) {
                if(!rc) rc = new Node(m + 1, r);
                rc->put(x, z);
            } else {
                if(!lc) lc = new Node(l, m);
                lc->put(x, z);
            }
        }
    }

    ll get(ll x, ll y){
        if(r < x || l > y) return 0;
        if(x <= l && r <= y) return v;
        ll ret = 0;
        if(lc) ret += lc->get(x, y);
        if(rc) ret += rc->get(x, y);
        return ret;
    }
};
Node *root;
bool check(){
    ll cur = 1, ma = root->v;
    while(cur < ma){
        ll t = root->get(0, cur - 1);
        if(t < cur) return false;
        cur = t + 1;
    }
    return true;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]){
    root = new Node(0, maxCoinSize - 1);
    F(i, coinsCount) root->put(coins[i] - 1, coins[i]);
    return check();
}

bool is_happy(int event, int coinsCount, long long coins[]){
    F(i, coinsCount) root->put(coins[i] - 1, event * coins[i]);
    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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 1884 KB Output is correct
7 Correct 2 ms 1884 KB Output is correct
8 Correct 19 ms 14068 KB Output is correct
9 Correct 19 ms 14172 KB Output is correct
10 Correct 17 ms 13660 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 259 ms 34544 KB Output is correct
7 Correct 255 ms 33876 KB Output is correct
8 Correct 267 ms 34384 KB Output is correct
9 Correct 394 ms 44116 KB Output is correct
10 Correct 437 ms 48212 KB Output is correct
11 Correct 115 ms 33364 KB Output is correct
12 Correct 114 ms 33220 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 1884 KB Output is correct
7 Correct 2 ms 1884 KB Output is correct
8 Correct 19 ms 14068 KB Output is correct
9 Correct 19 ms 14172 KB Output is correct
10 Correct 17 ms 13660 KB Output is correct
11 Correct 259 ms 34544 KB Output is correct
12 Correct 255 ms 33876 KB Output is correct
13 Correct 267 ms 34384 KB Output is correct
14 Correct 394 ms 44116 KB Output is correct
15 Correct 437 ms 48212 KB Output is correct
16 Correct 115 ms 33364 KB Output is correct
17 Correct 114 ms 33220 KB Output is correct
18 Correct 673 ms 226316 KB Output is correct
19 Correct 687 ms 234836 KB Output is correct
20 Correct 994 ms 380576 KB Output is correct
21 Correct 523 ms 199252 KB Output is correct
22 Correct 146 ms 39248 KB Output is correct
23 Correct 150 ms 39664 KB Output is correct
24 Correct 633 ms 216752 KB Output is correct