oj.uz

Submission #917864

# Submission time Handle Problem Language Result Execution time Memory
917864 2024-01-29T02:17:33 Z vjudge1 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1895 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[3<<23];
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 2392 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 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 2392 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 2396 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 5 ms 7000 KB Output is correct
8 Correct 39 ms 29788 KB Output is correct
9 Correct 41 ms 29788 KB Output is correct
10 Correct 35 ms 29992 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 2392 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 2396 KB Output is correct
6 Correct 1057 ms 66040 KB Output is correct
7 Correct 1043 ms 63744 KB Output is correct
8 Correct 1084 ms 65832 KB Output is correct
9 Correct 1895 ms 81548 KB Output is correct
10 Correct 1842 ms 88008 KB Output is correct
11 Correct 803 ms 57556 KB Output is correct
12 Correct 802 ms 57692 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 2392 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 2396 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 5 ms 7000 KB Output is correct
8 Correct 39 ms 29788 KB Output is correct
9 Correct 41 ms 29788 KB Output is correct
10 Correct 35 ms 29992 KB Output is correct
11 Correct 1057 ms 66040 KB Output is correct
12 Correct 1043 ms 63744 KB Output is correct
13 Correct 1084 ms 65832 KB Output is correct
14 Correct 1895 ms 81548 KB Output is correct
15 Correct 1842 ms 88008 KB Output is correct
16 Correct 803 ms 57556 KB Output is correct
17 Correct 802 ms 57692 KB Output is correct
18 Correct 1730 ms 435100 KB Output is correct
19 Correct 1628 ms 452824 KB Output is correct
20 Runtime error 1618 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -