oj.uz

Submission #275488

# Submission time Handle Problem Language Result Execution time Memory
275488 2020-08-20T06:15:17 Z 송준혁(#5101) Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 230396 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;
int num=1, lc[20202020], rc[20202020];
LL T[20202020], lz[20202020];
multiset<LL> S;

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

bool init(int N, long long _M, long long A[]) {
	M = _M;
	T[0]=T[1]=INF;
	for (int i=0; i<N; i++){
		upd(1, 1, M, A[i]+1, M, A[i]);
		if (S.find(A[i]) == S.end()) upd(1, 1, M, A[i], A[i], -INF-A[i]);
		S.insert(A[i]);
	}
	return T[1]>=-1;
}

bool is_happy(int e, int N, long long A[]) {
	if (e>0){
		for (int i=0; i<N; i++){
			upd(1, 1, M, A[i]+1, M, A[i]);
			if (S.find(A[i]) == S.end()) upd(1, 1, M, A[i], A[i], -INF-A[i]);
			S.insert(A[i]);
		}
	}
	else{
		for (int i=0; i<N; i++){
			upd(1, 1, M, A[i]+1, M, -A[i]);
			S.erase(S.find(A[i]));
			if (S.find(A[i]) == S.end()) upd(1, 1, M, A[i], A[i], INF+A[i]);
		}
	}
	return T[1]>=-1;
}

Compilation message

happiness.cpp: In function 'void upd(int, LL, LL, LL, LL, LL)':
happiness.cpp:19:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |  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 1 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 1 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 4 ms 1536 KB Output is correct
7 Correct 4 ms 1664 KB Output is correct
8 Correct 53 ms 10872 KB Output is correct
9 Correct 49 ms 10904 KB Output is correct
10 Correct 37 ms 10616 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 985 ms 27056 KB Output is correct
7 Correct 920 ms 26524 KB Output is correct
8 Correct 1157 ms 26744 KB Output is correct
9 Correct 1605 ms 32172 KB Output is correct
10 Correct 1971 ms 36932 KB Output is correct
11 Correct 578 ms 26352 KB Output is correct
12 Correct 579 ms 26408 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 4 ms 1536 KB Output is correct
7 Correct 4 ms 1664 KB Output is correct
8 Correct 53 ms 10872 KB Output is correct
9 Correct 49 ms 10904 KB Output is correct
10 Correct 37 ms 10616 KB Output is correct
11 Correct 985 ms 27056 KB Output is correct
12 Correct 920 ms 26524 KB Output is correct
13 Correct 1157 ms 26744 KB Output is correct
14 Correct 1605 ms 32172 KB Output is correct
15 Correct 1971 ms 36932 KB Output is correct
16 Correct 578 ms 26352 KB Output is correct
17 Correct 579 ms 26408 KB Output is correct
18 Correct 1679 ms 166348 KB Output is correct
19 Correct 1772 ms 172796 KB Output is correct
20 Execution timed out 2070 ms 230396 KB Time limit exceeded
21 Halted 0 ms 0 KB -