oj.uz

Submission #1114020

# Submission time Handle Problem Language Result Execution time Memory
1114020 2024-11-18T06:23:35 Z asli_bg Happiness (Balkan15_HAPPINESS) C++11
100 / 100
 1322 ms 380288 KB 
#include <bits/stdc++.h>
using namespace std;

#include "happiness.h"

//#define int long long

#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sp <<' '<<

#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)

#define cont(a) for(auto el:a) cout<<el<<' '; cout<<endl;
#define contp(a) for(auto el:a) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef long long ll;

#define endl '\n'

struct Dug{
    Dug *l,*r;
    //l--> sol çocuğum
    //r--> sag cocugum
    ll sum; //bas-son aralığının toplamı
    ll bas,son;

    Dug(ll bas,ll son) : l(nullptr) , r(nullptr), sum(0), bas(bas), son(son) {}
};

Dug *root;

void update(ll pos,ll val,Dug *nd){
    nd->sum+=val;
    ll bas=nd->bas;
    ll son=nd->son;
    if(bas==son) return; //leaf node
    
    ll mid=(bas+son)/2;

    //çocuklarım varsa
    if(pos<=mid){
        if(nd->l==nullptr) nd->l=new Dug(bas,mid);
        update(pos,val,nd->l);
    }
    else{
        if(nd->r==nullptr) nd->r=new Dug(mid+1,son);
        update(pos,val,nd->r);
    }
}

ll query(ll ql,ll qr,Dug *nd){
    ll bas=nd->bas;
    ll son=nd->son;

    if(ql>qr or bas>qr or son<ql) return 0;
    if(ql<=bas and son<=qr) return nd->sum;

    ll s1,s2;
    s1=s2=0;
    if(nd->l!=nullptr) s1=query(ql,qr,nd->l);
    if(nd->r!=nullptr) s2=query(ql,qr,nd->r);
    return s1+s2;
}

bool check(){
    ll cur=1;
    ll lim=root->sum;

    while(cur<=lim){
        ll top=query(1,cur,root);
        if(top<cur) return false;
        cur=top+1;
    }

    return true;
}

bool init(int n, long long m, long long coins[]) {

    root=new Dug(1,m);

    FOR(i,n) update(coins[i],coins[i],root);
    

	return check();
}

bool is_happy(int event, int n, long long coins[]) {
	FOR(i,n) update(coins[i],event*coins[i],root);
	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 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 2040 KB Output is correct
7 Correct 4 ms 2036 KB Output is correct
8 Correct 26 ms 14160 KB Output is correct
9 Correct 24 ms 14260 KB Output is correct
10 Correct 22 ms 13872 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 303 ms 34328 KB Output is correct
7 Correct 293 ms 34072 KB Output is correct
8 Correct 341 ms 34376 KB Output is correct
9 Correct 392 ms 44360 KB Output is correct
10 Correct 530 ms 48180 KB Output is correct
11 Correct 155 ms 33476 KB Output is correct
12 Correct 152 ms 33308 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 2040 KB Output is correct
7 Correct 4 ms 2036 KB Output is correct
8 Correct 26 ms 14160 KB Output is correct
9 Correct 24 ms 14260 KB Output is correct
10 Correct 22 ms 13872 KB Output is correct
11 Correct 303 ms 34328 KB Output is correct
12 Correct 293 ms 34072 KB Output is correct
13 Correct 341 ms 34376 KB Output is correct
14 Correct 392 ms 44360 KB Output is correct
15 Correct 530 ms 48180 KB Output is correct
16 Correct 155 ms 33476 KB Output is correct
17 Correct 152 ms 33308 KB Output is correct
18 Correct 797 ms 225904 KB Output is correct
19 Correct 912 ms 234772 KB Output is correct
20 Correct 1322 ms 380288 KB Output is correct
21 Correct 670 ms 199136 KB Output is correct
22 Correct 171 ms 39256 KB Output is correct
23 Correct 177 ms 39736 KB Output is correct
24 Correct 847 ms 216700 KB Output is correct