oj.uz

Submission #896220

# Submission time Handle Problem Language Result Execution time Memory
896220 2024-01-01T03:02:40 Z vjudge1 Happiness (Balkan15_HAPPINESS) C++17
10 / 100
 1014 ms 40268 KB 
#include "happiness.h"
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define N fhq[n]
random_device rd;
mt19937_64 rng(rd());
int tots, cnt;
//gp_hash_table<long long,long long> bit;
unordered_map<long long, long long> bit;
struct node {
    uint64_t key;
    int64_t lz,dif,val,cnt,mx;
    int l, r;
} fhq[1000100];
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(N.lz) {
        fhq[N.l].lz+=N.lz;
        fhq[N.r].lz+=N.lz;
        N.dif+=N.lz;
        N.mx+=N.lz;
        N.lz=0;
    }
}
void PU(int n) {
    N.mx=N.dif;
    if(N.l)
        pd(N.l),N.mx=max(fhq[N.l].mx,N.mx);
    if(N.r)
        pd(N.r),N.mx=max(fhq[N.r].mx,N.mx);
}
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].l),n=r;
    else merge(fhq[l].r,fhq[l].r,r),n=l;
    PU(n);
}
void split(int n, int &l, int &r, long long val) {
    if(!n)return void(l=r=0); pd(n);
    if(N.val<=val) split(N.r,N.r,r,val),l=n;
    else split(N.l,l,N.l,val),r=n;
    PU(n);
}
int find(int n, long long target) {
    if(!n)return n;
    if(N.val==target)return n;
    if(N.val>target)
        return find(N.l,target);
    return find(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-1);
        split(y,y,z,val);
        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:47:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   47 |     if(!n)return void(l=r=0); pd(n);
      |     ^~
happiness.cpp:47:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   47 |     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;
      |            ^~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 4 ms 3768 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1014 ms 40268 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 4 ms 3768 KB Output isn't correct
7 Halted 0 ms 0 KB -