oj.uz

Submission #736267

# Submission time Handle Problem Language Result Execution time Memory
736267 2023-05-05T11:32:22 Z Dan4Life Happiness (Balkan15_HAPPINESS) C++17
30 / 100
 519 ms 31176 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*4];
int L[mxN*4], R[mxN*4];
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 0 ms 212 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 1 ms 212 KB Output is correct
2 Correct 0 ms 212 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 724 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 24 ms 4796 KB Output is correct
9 Correct 23 ms 4868 KB Output is correct
10 Correct 23 ms 4736 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 0 ms 212 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 507 ms 14444 KB Output is correct
7 Correct 445 ms 15224 KB Output is correct
8 Correct 519 ms 15432 KB Output is correct
9 Runtime error 478 ms 31176 KB Execution killed with signal 11
10 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 0 ms 212 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 724 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 24 ms 4796 KB Output is correct
9 Correct 23 ms 4868 KB Output is correct
10 Correct 23 ms 4736 KB Output is correct
11 Correct 507 ms 14444 KB Output is correct
12 Correct 445 ms 15224 KB Output is correct
13 Correct 519 ms 15432 KB Output is correct
14 Runtime error 478 ms 31176 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -