oj.uz

Submission #568985

# Submission time Handle Problem Language Result Execution time Memory
568985 2022-05-26T12:05:39 Z Dan4Life Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1640 ms 133260 KB 
#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define fi first
#define se second
int IND = 0; ll mx;
vector<ll> segTree;
vector<pair<int,int>> child;

void add_node(ll v=0,int le=-1,int ri=-1){
    segTree.pb(v), child.pb({le,ri});
}

void update(ll i, ll v, int p=0, ll l=1, ll r=mx){
    if(l==r) { segTree[p]+=v; return; }
    ll mid = (l+r)/2;
    if(i<=mid){
        if(child[p].fi==-1) child[p].fi=++IND, add_node();
        update(i,v,child[p].fi,l,mid);
    }
    else{
        if(child[p].se==-1) child[p].se=++IND, add_node();
        update(i,v,child[p].se,mid+1,r);
    }
    ll le = child[p].fi==-1?0ll:segTree[child[p].fi];
    ll ri = child[p].se==-1?0ll:segTree[child[p].se];
    segTree[p] = le+ri;
}

ll query(ll i, ll j, int p=0, ll l=1, ll r=mx){
    if(i>r or j<l or i>j or p==-1) return 0ll;
    if(i<=l and r<=j) return segTree[p];
    ll mid = (l+r)/2;
    ll le = child[p].fi==-1?0ll:query(i,j,child[p].fi,l,mid);
    ll ri = child[p].se==-1?0ll:query(i,j,child[p].se,mid+1,r);
    return le+ri;
}

bool chk(){
    ll coin = 1;
    ll tot = query(1,mx);
    while(coin<=mx){
        ll sum = query(1,coin);
        if(sum+1>mx) return true;
        if(tot==sum) return true;
        if(query(coin+1,sum+1)==0) return false;
        coin = sum+1;
    }
    return true;
}

bool init(int n, ll M, ll a[]) {
    mx = M; add_node();
    for(int i = 0; i < n; i++) update(a[i],a[i]);
	return chk();
}

bool is_happy(int e, int n, ll a[]) {
    for(int i = 0; i < n; i++) update(a[i],a[i]*e);
	return chk();
}

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 304 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 304 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 3 ms 976 KB Output is correct
7 Correct 3 ms 1232 KB Output is correct
8 Correct 25 ms 6916 KB Output is correct
9 Correct 27 ms 6960 KB Output is correct
10 Correct 26 ms 6912 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 304 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 492 ms 15844 KB Output is correct
7 Correct 470 ms 16048 KB Output is correct
8 Correct 507 ms 15804 KB Output is correct
9 Correct 664 ms 20348 KB Output is correct
10 Correct 681 ms 21556 KB Output is correct
11 Correct 161 ms 15696 KB Output is correct
12 Correct 168 ms 15780 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 304 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 3 ms 976 KB Output is correct
7 Correct 3 ms 1232 KB Output is correct
8 Correct 25 ms 6916 KB Output is correct
9 Correct 27 ms 6960 KB Output is correct
10 Correct 26 ms 6912 KB Output is correct
11 Correct 492 ms 15844 KB Output is correct
12 Correct 470 ms 16048 KB Output is correct
13 Correct 507 ms 15804 KB Output is correct
14 Correct 664 ms 20348 KB Output is correct
15 Correct 681 ms 21556 KB Output is correct
16 Correct 161 ms 15696 KB Output is correct
17 Correct 168 ms 15780 KB Output is correct
18 Correct 1332 ms 104980 KB Output is correct
19 Correct 1367 ms 104800 KB Output is correct
20 Correct 1640 ms 133260 KB Output is correct
21 Correct 877 ms 70680 KB Output is correct
22 Correct 269 ms 17336 KB Output is correct
23 Correct 314 ms 17832 KB Output is correct
24 Correct 1316 ms 105120 KB Output is correct