oj.uz

Submission #1114018

# Submission time Handle Problem Language Result Execution time Memory
1114018 2024-11-18T06:22:13 Z asli_bg Happiness (Balkan15_HAPPINESS) C++11
40 / 100
 518 ms 524288 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;
    int bas=nd->bas;
    int 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 336 KB Output is correct
5 Correct 1 ms 608 KB Output is correct

Subtask #2
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 336 KB Output is correct
5 Correct 1 ms 608 KB Output is correct
6 Runtime error 518 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

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 336 KB Output is correct
5 Correct 1 ms 608 KB Output is correct
6 Correct 308 ms 37448 KB Output is correct
7 Correct 269 ms 37192 KB Output is correct
8 Correct 314 ms 37684 KB Output is correct
9 Correct 407 ms 48712 KB Output is correct
10 Correct 447 ms 52724 KB Output is correct
11 Correct 126 ms 37196 KB Output is correct
12 Correct 141 ms 37192 KB Output is correct

Subtask #4
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 336 KB Output is correct
5 Correct 1 ms 608 KB Output is correct
6 Runtime error 518 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -