oj.uz

Submission #917862

# Submission time Handle Problem Language Result Execution time Memory
917862 2024-01-29T02:15:16 Z vjudge1 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 524288 KB 
#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

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.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 2648 KB Output is correct
4 Correct 1 ms 2392 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 2396 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 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 4 ms 6748 KB Output is correct
8 Correct 40 ms 29872 KB Output is correct
9 Correct 38 ms 29788 KB Output is correct
10 Correct 39 ms 29780 KB Output is correct

Subtask #3
30.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 2648 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1081 ms 65816 KB Output is correct
7 Correct 987 ms 63804 KB Output is correct
8 Correct 1102 ms 66232 KB Output is correct
9 Correct 1873 ms 81988 KB Output is correct
10 Correct 1867 ms 88044 KB Output is correct
11 Correct 808 ms 57484 KB Output is correct
12 Correct 836 ms 57844 KB Output is correct

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 2648 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 4 ms 6748 KB Output is correct
8 Correct 40 ms 29872 KB Output is correct
9 Correct 38 ms 29788 KB Output is correct
10 Correct 39 ms 29780 KB Output is correct
11 Correct 1081 ms 65816 KB Output is correct
12 Correct 987 ms 63804 KB Output is correct
13 Correct 1102 ms 66232 KB Output is correct
14 Correct 1873 ms 81988 KB Output is correct
15 Correct 1867 ms 88044 KB Output is correct
16 Correct 808 ms 57484 KB Output is correct
17 Correct 836 ms 57844 KB Output is correct
18 Execution timed out 3720 ms 524288 KB Time limit exceeded
19 Halted 0 ms 0 KB -