oj.uz

Submission #917848

# Submission time Handle Problem Language Result Execution time Memory
917848 2024-01-29T02:00:35 Z vjudge1 Happiness (Balkan15_HAPPINESS) C++17
30 / 100
 2000 ms 78760 KB 
#include "happiness.h"
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define N T[i]
struct node {
    ll mx, lz;
    int lc, rc;
} T[1<<25];
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();
    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);
    upd(rt,val,val,val);
    if(!mp[val])
        upd(rt,val,val,val);
    mp[val]++;
}
void del(ll val) {
    upd(rt,val,val);
    upd(rt,-val,val,val);
    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:39:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     if(tl<=l+r>>1||N.lc)
      |            ~^~
happiness.cpp:40:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         upd(N.lc,v,tl,tr,l,l+r>>1ll);
      |                            ~^~
happiness.cpp:41:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     if(tr>l+r>>1||N.rc)
      |           ~^~
happiness.cpp:42:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         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 2 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
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 2 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 Correct 5 ms 6744 KB Output is correct
7 Correct 7 ms 6836 KB Output is correct
8 Correct 52 ms 29772 KB Output is correct
9 Correct 52 ms 29780 KB Output is correct
10 Correct 47 ms 29944 KB Output is correct

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 2 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 Correct 1366 ms 65936 KB Output is correct
7 Correct 1301 ms 63732 KB Output is correct
8 Correct 1374 ms 66104 KB Output is correct
9 Execution timed out 2021 ms 78760 KB Time limit exceeded
10 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 2 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 Correct 5 ms 6744 KB Output is correct
7 Correct 7 ms 6836 KB Output is correct
8 Correct 52 ms 29772 KB Output is correct
9 Correct 52 ms 29780 KB Output is correct
10 Correct 47 ms 29944 KB Output is correct
11 Correct 1366 ms 65936 KB Output is correct
12 Correct 1301 ms 63732 KB Output is correct
13 Correct 1374 ms 66104 KB Output is correct
14 Execution timed out 2021 ms 78760 KB Time limit exceeded
15 Halted 0 ms 0 KB -