Submission #896201

# Submission time Handle Problem Language Result Execution time Memory
896201 2024-01-01T02:20:58 Z vjudge1 Happiness (Balkan15_HAPPINESS) C++17
0 / 100
1 ms 2396 KB
#include "happiness.h"
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define O fhq[n].mx=max(max(fhq[fhq[n].l].mx,fhq[fhq[n].r].mx),fhq[n].dif);
random_device rd;
mt19937_64 rng(rd());
int tots, cnt;
gp_hash_table<long long,long long> bit;
struct node {
    uint64_t key;
    int64_t lz,dif,val,cnt,mx,llz,rlz;
    int l, r;
} fhq[2000100];
int root;
int nn(int val, int dif) {
    fhq[++cnt]={rng(),0,dif,val,1,dif,0,0};
    return cnt;
}
void pd(int n) {
    if(fhq[n].lz) {
        fhq[fhq[n].l].lz+=fhq[n].lz;
        fhq[fhq[n].r].lz+=fhq[n].lz;
        fhq[n].dif+=fhq[n].lz;
        fhq[n].mx+=fhq[n].lz;
        fhq[n].lz=0;
    }
}
void merge(int &n, int l, int r) {
    if(!l||!r) return void(n=l+r);
    pd(l),pd(r);
    if(fhq[l].key<fhq[r].key)
        merge(fhq[r].l, l,fhq[r].r),n=r;
    else merge(fhq[l].r,fhq[l].r,r),n=l;O
}
void split(int n, int &l, int &r, long long val) {
    if(!n)return void(l=r=0); pd(n);
    if(fhq[n].val<=val) split(fhq[n].r,fhq[n].r,r,val),l=n;
    else split(fhq[n].l,l,fhq[n].l,val),r=n;O
}
int find(int n, long long target) {
    if(!n)return n;
    if(fhq[n].val==target)return n;
    if(fhq[n].val<target)
        return find(fhq[n].l,target);
    return find(fhq[n].r,target);
}
void upd(long long pos, long long v) {
    int x, y;
    split(root,x,y,pos);
    fhq[y].lz+=v;
    merge(root,x,y);
    for(;pos<=1e12;pos+=pos&-pos)
        bit[pos]+=v;
}
void ins(long long val) {
    upd(val,-val);
    int x = find(root,val),y,z;
    if(x) fhq[x].cnt++;
    else {
        split(root,x,y,val);
        long long ch = 0;
        for(long long x = val-1; x; x-=x&-x)
            ch+=bit[x];
        z = nn(val,val+ch);
        merge(root,x,z);
        merge(root,root,y);
    }
}
void del(long long val) {
    upd(val,val);
    int x = find(root,val),y,z;
    if(fhq[x].cnt>1) fhq[x].cnt--;
    else {
        split(root,x,y,val);
        split(y,y,z,val+1);
        merge(root,x,z);
    }
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    root=nn(*coins,*coins);
    upd(*coins,-*coins);
    for(int i = 1; i < coinsCount; i++)
        ins(coins[i]);
    return fhq[root].mx<2;
}
bool is_happy(int event, int coinsCount, long long coins[]) {
	for(int i = 0; i < coinsCount; i++)
        (event+1?ins:del)(coins[i]);
    return fhq[root].mx<2;
}

Compilation message

happiness.cpp: In function 'void split(int, int&, int&, long long int)':
happiness.cpp:38:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   38 |     if(!n)return void(l=r=0); pd(n);
      |     ^~
happiness.cpp:38:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   38 |     if(!n)return void(l=r=0); pd(n);
      |                               ^~
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 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -