This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "happiness.h"
//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define vi vector<int>
#define all(xx) xx.begin(),xx.end()
const int inf = 1e18;
int LIM;
struct Node {
int lazy = 0;
pii val = {inf,0};
Node *l=nullptr, *r=nullptr;
void push() {
if (!lazy) return;
val.ss+=lazy;
if (!l) l = new Node;
if (!r) r = new Node;
l->lazy+=lazy;
r->lazy+=lazy;
lazy = 0;
}
} *root = new Node;
pii cmp(const pii& p1,const pii& p2) {
if (p1.ff == inf) return p2;
if (p2.ff == inf) return p1;
return (p1.second < p2.second)?p1:p2;
}
pii vall(const Node* node){
return (!node)? pii{inf,inf} : node->val;
}
void insert(Node* node,int l,int r,int p) {
node->push();
if (l == r) {
if (node->val.ff == inf) {
node->val.ff = 1;
node->val.ss -= 2*p;
}
else node->val.ff++;
return;
}
int m = (l+r) >> 1;
if (p <= m) {
if (!node->l) node->l = new Node;
insert(node->l,l,m,p);
}
else{
if (!node->r) node->r = new Node;
insert(node->r,m+1,r,p);
}
node->val = cmp(vall(node->l),vall(node->r));
}
void remove(Node* node,int l,int r,int p) {
node->push();
if (l == r) {
if (node->val.ff == 1) {
node->val.ff = inf;
node->val.ss+=2*p;
}
else node->val.ff--;
return;
}
int m = (l+r) >> 1;
if (p <= m) {
if (!node->l) node->l = new Node;
remove(node->l,l,m,p);
}
else{
if (!node->r) node->r = new Node;
remove(node->r,m+1,r,p);
}
node->val = cmp(vall(node->l),vall(node->r));
}
void prop(Node* node,int l,int r,int L,int R,int v) {
node->push();
if (l >= L && r <= R) {
node->lazy+=v;
node->push();
return;
}
int m = (l+r) >> 1;
if (!node->l) node->l = new Node;
if (!node->r) node->r = new Node;
if (m >= L) prop(node->l,l,m,L,R,v);
if (m+1<=R) prop(node->r,m+1,r,L,R,v);
node->l->push(),node->r->push();
node->val = cmp(node->l->val,node->r->val);
}
pii query(Node* node,int l,int r,int p) {
node->push();
if (l == r) return node->val;
int m = (l+r) >> 1;
if (!node->l) node->l = new Node;
if (!node->r) node->r = new Node;
if (p <= m) return query(node->l,l,m,p);
else return query(node->r,m+1,r,p);
}
bool init(int32_t coinsCount, long long maxCoinSize, long long coins[]) {
LIM = maxCoinSize;
for (int i=0;i<coinsCount;i++) {
insert(root,1,LIM,coins[i]);
prop(root,1,LIM,coins[i],LIM,coins[i]);
}
root->push();
return (root->val.ff==inf || root->val.ss >= -1);
}
bool is_happy(int32_t event, int32_t coinsCount, long long coins[]) {
if (event == -1) {
for (int i=0;i<coinsCount;i++) {
remove(root,1,LIM,coins[i]);
prop(root,1,LIM,coins[i],LIM,-coins[i]);
}
}
else {
for (int i=0;i<coinsCount;i++) {
insert(root,1,LIM,coins[i]);
prop(root,1,LIM,coins[i],LIM,coins[i]);
}
}
root->push();
return (root->val.ff==inf || root->val.ss >= -1);
}
Compilation message (stderr)
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |