oj.uz

Submission #736266

# Submission time Handle Problem Language Result Execution time Memory
736266 2023-05-05T11:31:21 Z Dan4Life Happiness (Balkan15_HAPPINESS) C++17
30 / 100
 46 ms 15552 KB 
#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = (int)2e5+10;
ll mx, segTree[mxN*2];
int L[mxN*2], R[mxN*2];
int IND = 1;

void upd(ll x, ll v, int p=1, ll l=1, ll r=mx){
	if(l==r){ segTree[p]+=v; return; }
	ll mid = (l+r)/2;
	if(x<=mid){
		if(!L[p]) L[p]=++IND;
		upd(x,v,L[p],l,mid);
	}
	else{
		if(!R[p]) R[p]=++IND;
		upd(x,v,R[p],mid+1,r);
	}
	segTree[p]= segTree[L[p]]+segTree[R[p]];
}

ll query(ll i, ll j, int p=1, ll l=1, ll r=mx){
	if(i>r or j<l or i>j or !p) return 0;
	if(i<=l and r<=j) return segTree[p];
	ll mid = (l+r)/2;
	return query(i,j,L[p],l,mid)+query(i,j,R[p],mid+1,r);
}

bool chk(){
    ll coin = 1, 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;
    for(int i = 0; i < n; i++) upd(a[i],a[i]);
	return chk();
}

bool is_happy(int e, int n, ll a[]) {
    for(int i = 0; i < n; i++) upd(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 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 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 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 2 ms 832 KB Output is correct
8 Correct 23 ms 5008 KB Output is correct
9 Correct 23 ms 5076 KB Output is correct
10 Correct 23 ms 4928 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Runtime error 46 ms 15552 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 2 ms 832 KB Output is correct
8 Correct 23 ms 5008 KB Output is correct
9 Correct 23 ms 5076 KB Output is correct
10 Correct 23 ms 4928 KB Output is correct
11 Runtime error 46 ms 15552 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -