oj.uz

Submission #917866

# Submission time Handle Problem Language Result Execution time Memory
917866 2024-01-29T02:18:40 Z vjudge1 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1885 ms 514592 KB 
#include "happiness.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N T[i]
struct node {
    ll mx, lz;
    int lc, rc;
} T[5<<22];
map<ll, int> mp;
int rt, cnt;
int nn() {
    T[++cnt]={0,0,0,0};
    return cnt;
}
void pd(int i) {
    if(N.lz) {
        N.mx+=N.lz;
        if(!N.lc)
            N.lc=nn();
        if(!N.rc)
            N.rc=nn();
        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=nn();
    pd(i);
    if(tl>r||tr<l)
        return;
    if(tl<=l&&r<=tr) {
        N.lz+=v;
        pd(i);
        return;
    }
    upd(N.lc,v,tl,tr,l,l+r>>1ll);
    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

happiness.cpp: In function 'void upd(int&, long long int, long long int, long long int, long long int, long long int)':
happiness.cpp:38:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     upd(N.lc,v,tl,tr,l,l+r>>1ll);
      |                        ~^~
happiness.cpp:39:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     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.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 6 ms 6748 KB Output is correct
8 Correct 42 ms 29784 KB Output is correct
9 Correct 39 ms 29776 KB Output is correct
10 Correct 35 ms 29776 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1073 ms 66088 KB Output is correct
7 Correct 1016 ms 63652 KB Output is correct
8 Correct 1068 ms 65856 KB Output is correct
9 Correct 1874 ms 81452 KB Output is correct
10 Correct 1885 ms 88060 KB Output is correct
11 Correct 793 ms 57572 KB Output is correct
12 Correct 790 ms 57780 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 6 ms 6748 KB Output is correct
8 Correct 42 ms 29784 KB Output is correct
9 Correct 39 ms 29776 KB Output is correct
10 Correct 35 ms 29776 KB Output is correct
11 Correct 1073 ms 66088 KB Output is correct
12 Correct 1016 ms 63652 KB Output is correct
13 Correct 1068 ms 65856 KB Output is correct
14 Correct 1874 ms 81452 KB Output is correct
15 Correct 1885 ms 88060 KB Output is correct
16 Correct 793 ms 57572 KB Output is correct
17 Correct 790 ms 57780 KB Output is correct
18 Correct 1669 ms 435268 KB Output is correct
19 Correct 1575 ms 452584 KB Output is correct
20 Incorrect 1602 ms 514592 KB Output isn't correct
21 Halted 0 ms 0 KB -