oj.uz

Submission #736271

# Submission time Handle Problem Language Result Execution time Memory
736271 2023-05-05T11:36:57 Z Dan4Life Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1006 ms 120612 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*18];
int L[mxN*18], R[mxN*18];
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 280 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 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 280 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 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 724 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 28 ms 5004 KB Output is correct
9 Correct 27 ms 4956 KB Output is correct
10 Correct 27 ms 4792 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 280 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 551 ms 12516 KB Output is correct
7 Correct 543 ms 12200 KB Output is correct
8 Correct 596 ms 12340 KB Output is correct
9 Correct 703 ms 16500 KB Output is correct
10 Correct 579 ms 21320 KB Output is correct
11 Correct 154 ms 15116 KB Output is correct
12 Correct 201 ms 15264 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 280 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 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 724 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 28 ms 5004 KB Output is correct
9 Correct 27 ms 4956 KB Output is correct
10 Correct 27 ms 4792 KB Output is correct
11 Correct 551 ms 12516 KB Output is correct
12 Correct 543 ms 12200 KB Output is correct
13 Correct 596 ms 12340 KB Output is correct
14 Correct 703 ms 16500 KB Output is correct
15 Correct 579 ms 21320 KB Output is correct
16 Correct 154 ms 15116 KB Output is correct
17 Correct 201 ms 15264 KB Output is correct
18 Runtime error 1006 ms 120612 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -