oj.uz

Submission #275654

# Submission time Handle Problem Language Result Execution time Memory
275654 2020-08-20T06:56:05 Z 송준혁(#5101) Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1663 ms 124932 KB 
#include "happiness.h"
#include <bits/stdc++.h>
#define INF (1ll<<61)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

LL M, sum;
int num=1, lc[20202020], rc[20202020];
LL T[20202020];

void upd(int id, LL s, LL e, LL t, LL v){
	if (e < t || t < s) return;
	if (s == e){
		T[id] += v;
		return;
	}
	LL m=s+e>>1;
	if (!lc[id] && t <= m) lc[id]=++num;
	if (!rc[id] && t > m) rc[id]=++num;
	upd(lc[id], s, m, t, v);
	upd(rc[id], m+1, e, t, v);
	T[id] = T[lc[id]] + T[rc[id]];
}

LL qry(int id, LL s, LL e, LL ts, LL te){
	if (e < ts || te < s || !id) return 0;
	if (ts <= s && e <= te) return T[id];
	LL m=s+e>>1;
	return qry(lc[id], s, m, ts, te)+qry(rc[id], m+1, e, ts, te);
}

bool chk(){
	LL t=0;
	while (t<sum){
		LL x = qry(1, 1, M, 1, t+1);
		if (x == t) return false;
		t = x;
	}
	return true;
}

bool init(int N, long long _M, long long A[]) {
	M = _M;
	for (int i=0; i<N; i++) upd(1, 1, M, A[i], A[i]), sum+=A[i];
	return chk();
}

bool is_happy(int e, int N, long long A[]) {
	for (int i=0; i<N; i++){
		upd(1, 1, M, A[i], e*A[i]);
		sum+=e*A[i];
	}
	return chk();
}

Compilation message

happiness.cpp: In function 'void upd(int, LL, LL, LL, LL)':
happiness.cpp:18:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |  LL m=s+e>>1;
      |       ~^~
happiness.cpp: In function 'LL qry(int, LL, LL, LL, LL)':
happiness.cpp:29:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |  LL m=s+e>>1;
      |       ~^~
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 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 30 ms 4984 KB Output is correct
9 Correct 30 ms 4992 KB Output is correct
10 Correct 28 ms 4864 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 556 ms 12536 KB Output is correct
7 Correct 561 ms 12300 KB Output is correct
8 Correct 618 ms 12536 KB Output is correct
9 Correct 816 ms 15608 KB Output is correct
10 Correct 883 ms 17024 KB Output is correct
11 Correct 266 ms 11512 KB Output is correct
12 Correct 241 ms 11436 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 30 ms 4984 KB Output is correct
9 Correct 30 ms 4992 KB Output is correct
10 Correct 28 ms 4864 KB Output is correct
11 Correct 556 ms 12536 KB Output is correct
12 Correct 561 ms 12300 KB Output is correct
13 Correct 618 ms 12536 KB Output is correct
14 Correct 816 ms 15608 KB Output is correct
15 Correct 883 ms 17024 KB Output is correct
16 Correct 266 ms 11512 KB Output is correct
17 Correct 241 ms 11436 KB Output is correct
18 Correct 1259 ms 74408 KB Output is correct
19 Correct 1228 ms 77432 KB Output is correct
20 Correct 1663 ms 124932 KB Output is correct
21 Correct 888 ms 68984 KB Output is correct
22 Correct 423 ms 14584 KB Output is correct
23 Correct 425 ms 14200 KB Output is correct
24 Correct 1134 ms 74512 KB Output is correct