Submission #917862

#	Time	Username	Problem	Language	Result	Execution time	Memory
917862		vjudge1	Happiness (Balkan15_HAPPINESS)	C++17	60 / 100	3720 ms	524288 KiB

happiness

#include "happiness.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N T[i]
struct node {
    ll mx=0, lz=0;
    int lc=0,rc=0;
} T[1<<24];
map<ll, int> mp;
int rt, cnt;
void pd(int i) {
    if(N.lz) {
        N.mx+=N.lz;
        if(!N.lc)
            N.lc=++cnt;
        if(!N.rc)
            N.rc=++cnt;
        T[N.lc].lz+=N.lz;
        T[N.rc].lz+=N.lz;
    }
    N.lz=0;
}
void upd(int &i,ll v,ll tl,ll tr=1e12,ll l=1,ll r=1e12) {
    if(!i) i=++cnt;
    else pd(i);
    if(tl>r||tr<l)
        return;
    if(tl<=l&&r<=tr) {
        N.lz+=v;
        pd(i);
        return;
    }
    if(tl<=l+r>>1||N.lc)
        upd(N.lc,v,tl,tr,l,l+r>>1ll);
    if(tr>l+r>>1||N.rc)
        upd(N.rc,v,tl,tr,l+r+2>>1,r);
    N.mx=max(T[N.lc].mx,T[N.rc].mx);
}
void add(ll val) {
    upd(rt,-val,val+1);
    if(!mp[val])
        upd(rt,val,val,val);
    mp[val]++;
}
void del(ll val) {
    upd(rt,val,val+1);
    mp[val]--;
    if(!mp[val])
        upd(rt,-val,val,val);
}
bool init(int coinsCount, ll maxCoinSize, ll coins[]) {
    for(int i=0;i<coinsCount;i++)
        add(coins[i]);
    return T[rt].mx<2;
}
bool is_happy(int event, int coinsCount, ll coins[]) {
	for(int i=0;i<coinsCount;i++)
        (event+1?add:del)(coins[i]);
    return T[rt].mx<2;
}

Compilation message (stderr)

happiness.cpp: In function 'void upd(int&, long long int, long long int, long long int, long long int, long long int)':
happiness.cpp:34:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     if(tl<=l+r>>1||N.lc)
      |            ~^~
happiness.cpp:35:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         upd(N.lc,v,tl,tr,l,l+r>>1ll);
      |                            ~^~
happiness.cpp:36:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     if(tr>l+r>>1||N.rc)
      |           ~^~
happiness.cpp:37:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         upd(N.rc,v,tl,tr,l+r+2>>1,r);
      |                          ~~~^~
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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40