# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
275433 |
2020-08-20T06:03:23 Z |
송준혁(#5101) |
Happiness (Balkan15_HAPPINESS) |
C++17 |
|
2000 ms |
292468 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 busy(int id){
if (!lz[id]) return;
if (!rc[id]) rc[id]=++num, T[num]=INF;
if (!lc[id]) lc[id]=++num, T[num]=INF;
T[lc[id]] += lz[id], lz[lc[id]] += lz[id];
T[rc[id]] += lz[id], lz[rc[id]] += lz[id];
lz[id] = 0;
}
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;
}
busy(id);
LL m=s+e>>1;
if (!rc[id] && te > m) rc[id]=++num, T[num]=INF;
if (!lc[id] && ts <= m) lc[id]=++num, T[num]=INF;
upd(rc[id], m+1, e, ts, te, v);
upd(lc[id], s, m, ts, te, v);
T[id] = min(T[lc[id]], T[rc[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: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;
| ^~~~~~~~
# |
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 |
# |
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 |
5 ms |
1920 KB |
Output is correct |
7 |
Correct |
5 ms |
2048 KB |
Output is correct |
8 |
Correct |
51 ms |
13944 KB |
Output is correct |
9 |
Correct |
51 ms |
14152 KB |
Output is correct |
10 |
Correct |
53 ms |
13688 KB |
Output is correct |
# |
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 |
1067 ms |
30616 KB |
Output is correct |
7 |
Correct |
1016 ms |
30560 KB |
Output is correct |
8 |
Correct |
1038 ms |
30712 KB |
Output is correct |
9 |
Correct |
1976 ms |
36580 KB |
Output is correct |
10 |
Correct |
1934 ms |
41340 KB |
Output is correct |
11 |
Correct |
591 ms |
26352 KB |
Output is correct |
12 |
Correct |
600 ms |
26360 KB |
Output is correct |
# |
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 |
5 ms |
1920 KB |
Output is correct |
7 |
Correct |
5 ms |
2048 KB |
Output is correct |
8 |
Correct |
51 ms |
13944 KB |
Output is correct |
9 |
Correct |
51 ms |
14152 KB |
Output is correct |
10 |
Correct |
53 ms |
13688 KB |
Output is correct |
11 |
Correct |
1067 ms |
30616 KB |
Output is correct |
12 |
Correct |
1016 ms |
30560 KB |
Output is correct |
13 |
Correct |
1038 ms |
30712 KB |
Output is correct |
14 |
Correct |
1976 ms |
36580 KB |
Output is correct |
15 |
Correct |
1934 ms |
41340 KB |
Output is correct |
16 |
Correct |
591 ms |
26352 KB |
Output is correct |
17 |
Correct |
600 ms |
26360 KB |
Output is correct |
18 |
Correct |
1714 ms |
215948 KB |
Output is correct |
19 |
Correct |
1701 ms |
224156 KB |
Output is correct |
20 |
Execution timed out |
2103 ms |
292468 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |