| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 275380 |
2020-08-20T05:46:43 Z |
임성재(#5103) |
Happiness (Balkan15_HAPPINESS) |
C++17 |
|
1 ms |
288 KB |
#include "happiness.h"
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;
ll n, m;
int chk[1000010];
ll tree[4000010];
ll lazy[4000010];
void Init(int node, int s, int e) {
tree[node] = INF - e;
if(s == e) return;
Init(node*2, s, (s+e)/2);
Init(node*2+1, (s+e)/2+1, e);
}
void propagate(int node, int s, int e) {
tree[node] += lazy[node];
if(s != e) {
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0;
}
void update(int node, int s, int e, int l, int r, ll x) {
propagate(node, s, e);
if(r < s || e < l) return;
if(l <= s && e <= r) {
lazy[node] += x;
propagate(node, s, e);
return;
}
update(node*2, s, (s+e)/2, l, r, x);
update(node*2+1, (s+e)/2+s, e, l, r, x);
tree[node] = min(tree[node*2], tree[node*2+1]);
}
void chg(int node, int s, int e, int i, ll x) {
propagate(node, s, e);
if(s == e) {
tree[node] += x;
return;
}
int m = s + e >> 1;
if(i <= m) chg(node*2, s, m, i, x);
else chg(node*2+1, m+1, e, i, x);
tree[node] = min(tree[node*2], tree[node*2+1]);
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
n = coinsCount;
m = maxCoinSize;
m++;
Init(1, 1, m);
for(int i=0; i<n; i++) {
if(chk[coins[i]]) chg(1, 1, m, coins[i], INF);
update(1, 1, m, coins[i]+1, m, coins[i]);
chk[coins[i]]++;
if(chk[coins[i]]) chg(1, 1, m, coins[i], -INF);
}
propagate(1, 1, m);
return tree[1] >= -1;
}
bool is_happy(int event, int coinsCount, long long coins[]) {
n = coinsCount;
for(int i=0; i<n; i++) {
if(chk[coins[i]]) chg(1, 1, m, coins[i], INF);
update(1, 1, m, coins[i]+1, m, coins[i] * event);
chk[coins[i]] += event;
if(chk[coins[i]]) chg(1, 1, m, coins[i], -INF);
}
propagate(1, 1, m);
return tree[1] >= -1;
}
Compilation message
happiness.cpp: In function 'void chg(int, int, int, int, ll)':
happiness.cpp:67:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
67 | int m = s + e >> 1;
| ~~^~~
grader.cpp: In function 'int main()':
grader.cpp:14:9: warning: unused variable 'd' [-Wunused-variable]
14 | int i, d;
| ^
grader.cpp:15:12: warning: unused variable 'max_code' [-Wunused-variable]
15 | long long max_code;
| ^~~~~~~~
grader.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
17 | scanf("%d%lld", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~~~
grader.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
19 | scanf("%lld", &coins[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~
grader.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
23 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
grader.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
26 | scanf("%d%d", &ck, &c);
| ~~~~~^~~~~~~~~~~~~~~~~
grader.cpp:28:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
28 | scanf("%lld", &A[j]);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
