oj.uz

Submission #917863

# Submission time Handle Problem Language Result Execution time Memory
917863 2024-01-29T02:16:18 Z vjudge1 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1862 ms 407988 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<<24];
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 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 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 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 4 ms 6840 KB Output is correct
8 Correct 40 ms 29976 KB Output is correct
9 Correct 40 ms 29776 KB Output is correct
10 Correct 36 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 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 1071 ms 65988 KB Output is correct
7 Correct 1048 ms 63796 KB Output is correct
8 Correct 1134 ms 66248 KB Output is correct
9 Correct 1748 ms 81820 KB Output is correct
10 Correct 1862 ms 88212 KB Output is correct
11 Correct 789 ms 57428 KB Output is correct
12 Correct 797 ms 57356 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 2 ms 2396 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 4 ms 6840 KB Output is correct
8 Correct 40 ms 29976 KB Output is correct
9 Correct 40 ms 29776 KB Output is correct
10 Correct 36 ms 29776 KB Output is correct
11 Correct 1071 ms 65988 KB Output is correct
12 Correct 1048 ms 63796 KB Output is correct
13 Correct 1134 ms 66248 KB Output is correct
14 Correct 1748 ms 81820 KB Output is correct
15 Correct 1862 ms 88212 KB Output is correct
16 Correct 789 ms 57428 KB Output is correct
17 Correct 797 ms 57356 KB Output is correct
18 Incorrect 1473 ms 407988 KB Output isn't correct
19 Halted 0 ms 0 KB -