oj.uz

Submission #917892

# Submission time Handle Problem Language Result Execution time Memory
917892 2024-01-29T03:07:48 Z vjudge1 Happiness (Balkan15_HAPPINESS) C++17
30 / 100
 2000 ms 88040 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();
    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 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 1 ms 2396 KB Output is correct
6 Correct 4 ms 6784 KB Output is correct
7 Correct 5 ms 6748 KB Output is correct
8 Correct 46 ms 29872 KB Output is correct
9 Correct 43 ms 29784 KB Output is correct
10 Correct 36 ms 29916 KB Output is correct

Subtask #3
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 2396 KB Output is correct
6 Correct 1104 ms 65792 KB Output is correct
7 Correct 1155 ms 63576 KB Output is correct
8 Correct 1137 ms 65924 KB Output is correct
9 Correct 1878 ms 81656 KB Output is correct
10 Execution timed out 2041 ms 88040 KB Time limit exceeded
11 Halted 0 ms 0 KB -

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 2396 KB Output is correct
6 Correct 4 ms 6784 KB Output is correct
7 Correct 5 ms 6748 KB Output is correct
8 Correct 46 ms 29872 KB Output is correct
9 Correct 43 ms 29784 KB Output is correct
10 Correct 36 ms 29916 KB Output is correct
11 Correct 1104 ms 65792 KB Output is correct
12 Correct 1155 ms 63576 KB Output is correct
13 Correct 1137 ms 65924 KB Output is correct
14 Correct 1878 ms 81656 KB Output is correct
15 Execution timed out 2041 ms 88040 KB Time limit exceeded
16 Halted 0 ms 0 KB -