oj.uz

Submission #917840

# Submission time Handle Problem Language Result Execution time Memory
917840 2024-01-29T01:51:23 Z vjudge1 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1830 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, 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+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:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     if(tl<=l+r>>1||N.lc)
      |            ~^~
happiness.cpp:39:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         upd(N.lc,v,tl,tr,l,l+r>>1ll);
      |                            ~^~
happiness.cpp:40:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     if(tr>l+r>>1||N.rc)
      |           ~^~
happiness.cpp:41:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         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 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 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 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 5 ms 6748 KB Output is correct
8 Correct 43 ms 29980 KB Output is correct
9 Correct 42 ms 29776 KB Output is correct
10 Correct 41 ms 29952 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 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1089 ms 66132 KB Output is correct
7 Correct 1066 ms 63632 KB Output is correct
8 Correct 1070 ms 66132 KB Output is correct
9 Correct 1781 ms 81488 KB Output is correct
10 Correct 1830 ms 88320 KB Output is correct
11 Correct 886 ms 57528 KB Output is correct
12 Correct 870 ms 57424 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 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 5 ms 6748 KB Output is correct
8 Correct 43 ms 29980 KB Output is correct
9 Correct 42 ms 29776 KB Output is correct
10 Correct 41 ms 29952 KB Output is correct
11 Correct 1089 ms 66132 KB Output is correct
12 Correct 1066 ms 63632 KB Output is correct
13 Correct 1070 ms 66132 KB Output is correct
14 Correct 1781 ms 81488 KB Output is correct
15 Correct 1830 ms 88320 KB Output is correct
16 Correct 886 ms 57528 KB Output is correct
17 Correct 870 ms 57424 KB Output is correct
18 Correct 1638 ms 435488 KB Output is correct
19 Correct 1619 ms 452468 KB Output is correct
20 Runtime error 1646 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -