oj.uz

Submission #736272

# Submission time Handle Problem Language Result Execution time Memory
736272 2023-05-05T11:38:23 Z Dan4Life Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1629 ms 133024 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*40];
int L[mxN*40], R[mxN*40];
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 0 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 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 22 ms 4796 KB Output is correct
9 Correct 26 ms 4884 KB Output is correct
10 Correct 21 ms 4716 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 445 ms 12264 KB Output is correct
7 Correct 438 ms 12204 KB Output is correct
8 Correct 548 ms 12312 KB Output is correct
9 Correct 657 ms 15500 KB Output is correct
10 Correct 590 ms 16892 KB Output is correct
11 Correct 168 ms 11452 KB Output is correct
12 Correct 133 ms 11404 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 22 ms 4796 KB Output is correct
9 Correct 26 ms 4884 KB Output is correct
10 Correct 21 ms 4716 KB Output is correct
11 Correct 445 ms 12264 KB Output is correct
12 Correct 438 ms 12204 KB Output is correct
13 Correct 548 ms 12312 KB Output is correct
14 Correct 657 ms 15500 KB Output is correct
15 Correct 590 ms 16892 KB Output is correct
16 Correct 168 ms 11452 KB Output is correct
17 Correct 133 ms 11404 KB Output is correct
18 Correct 1227 ms 75648 KB Output is correct
19 Correct 1314 ms 82736 KB Output is correct
20 Correct 1629 ms 133024 KB Output is correct
21 Correct 825 ms 70528 KB Output is correct
22 Correct 219 ms 17168 KB Output is correct
23 Correct 235 ms 17676 KB Output is correct
24 Correct 1216 ms 76764 KB Output is correct