oj.uz

Submission #917834

# Submission time Handle Problem Language Result Execution time Memory
917834 2024-01-29T01:37:23 Z vjudge1 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1729 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();
    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 2396 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2492 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 2648 KB Output is correct
3 Correct 1 ms 2492 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 5 ms 6744 KB Output is correct
8 Correct 42 ms 30032 KB Output is correct
9 Correct 40 ms 30036 KB Output is correct
10 Correct 36 ms 30028 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 2648 KB Output is correct
3 Correct 1 ms 2492 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 984 ms 69276 KB Output is correct
7 Correct 993 ms 66744 KB Output is correct
8 Correct 1020 ms 68992 KB Output is correct
9 Correct 1643 ms 86088 KB Output is correct
10 Correct 1729 ms 92708 KB Output is correct
11 Correct 783 ms 61524 KB Output is correct
12 Correct 775 ms 61296 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 2648 KB Output is correct
3 Correct 1 ms 2492 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 5 ms 6744 KB Output is correct
8 Correct 42 ms 30032 KB Output is correct
9 Correct 40 ms 30036 KB Output is correct
10 Correct 36 ms 30028 KB Output is correct
11 Correct 984 ms 69276 KB Output is correct
12 Correct 993 ms 66744 KB Output is correct
13 Correct 1020 ms 68992 KB Output is correct
14 Correct 1643 ms 86088 KB Output is correct
15 Correct 1729 ms 92708 KB Output is correct
16 Correct 783 ms 61524 KB Output is correct
17 Correct 775 ms 61296 KB Output is correct
18 Correct 1558 ms 440700 KB Output is correct
19 Correct 1547 ms 458152 KB Output is correct
20 Runtime error 1510 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -