oj.uz

Submission #887608

# Submission time Handle Problem Language Result Execution time Memory
887608 2023-12-14T20:16:34 Z MarwenElarbi Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1006 ms 524288 KB 
#include <bits/stdc++.h>
//#include "happiness.h"
#include <stdio.h>
#include <stdlib.h>

#define NMAX 200000
#define QMAX 100000

static int N, Q;
static long long M;
static long long coins[NMAX], A[5];
using namespace std;
struct Node{
    long long lazy, l, r, cnt, tl, tr;
    double long ans;
    Node(): lazy(0), ans(0), l(-1), r(-1), cnt(0) {}
};
Node segtree[123456*64];
int cnt=0;
void push_down(int pos){
    long long mid=(segtree[pos].tl+segtree[pos].tr)/2;
    if(segtree[pos].l==-1){
        segtree[pos].l=++cnt;
        segtree[segtree[pos].l].tl=segtree[pos].tl;
        segtree[segtree[pos].l].tr=mid;
    }
    if(segtree[pos].r==-1){
        segtree[pos].r=++cnt;
        segtree[segtree[pos].r].tl=mid+1;
        segtree[segtree[pos].r].tr=segtree[pos].tr;
    }
    return;
}
void expand(int pos){
    if(segtree[pos].lazy!=0){
        push_down(pos);
        segtree[segtree[pos].l].ans+=segtree[pos].lazy;
        segtree[segtree[pos].r].ans+=segtree[pos].lazy;
        segtree[segtree[pos].l].lazy+=segtree[pos].lazy;
        segtree[segtree[pos].r].lazy+=segtree[pos].lazy;
        segtree[pos].lazy=0;
    }
}
void update(int pos,long long left,long long right,long long value)
{
    expand(pos);
    if(left==segtree[pos].tl&&right==segtree[pos].tr){
        //cout<<segtree[pos].tl<<" "<<segtree[pos].tr<<" "<<value<<endl;
        segtree[pos].lazy+=value;
        segtree[pos].ans+=value;
        expand(pos);
        return;
    }
    long long mid=(segtree[pos].tl+segtree[pos].tr)/2;
    push_down(pos);
    if(left>mid) update(segtree[pos].r,left,right,value);
    else if(right<=mid) update(segtree[pos].l,left,right,value);
    else{
        update(segtree[pos].l,left,mid,value);
        update(segtree[pos].r,mid+1,right,value);
    }
    segtree[pos].ans=min(segtree[segtree[pos].l].ans,segtree[segtree[pos].r].ans);
    return;
}
void query(int pos,long long index,int event){
    //cout <<segtree[pos].tl<<" "<<segtree[pos].tr<<endl;
    expand(pos);
    if(segtree[pos].tl==segtree[pos].tr){
        if(event==1){
            if(segtree[pos].cnt==0) segtree[pos].ans-=index;
            segtree[pos].cnt++;
        }else{
            segtree[pos].cnt--;
            if(segtree[pos].cnt==0) segtree[pos].ans+=index;
        }
        //cout <<segtree[pos].tl<<" "<<segtree[pos].sum<<" "<<segtree[pos].ans<<endl;
        return;
    }
    push_down(pos);
    long long mid=(segtree[pos].tl+segtree[pos].tr)/2;
    if(index<=mid) query(segtree[pos].l,index,event);
    else query(segtree[pos].r,index,event);
    segtree[pos].ans=min(segtree[segtree[pos].l].ans,segtree[segtree[pos].r].ans);
    return;
}
long long mx;
bool init(int coinsCount, long long maxCoinSize, long long coins[]){
    sort(coins,coins+coinsCount);
    segtree[0].tl=0;
    segtree[0].tr=maxCoinSize;
    mx=maxCoinSize;
    update(0,0,mx,1);
    for (int i = 0; i < coinsCount; ++i)
    {
        query(0,coins[i],1);
        update(0,coins[i]+1,maxCoinSize,coins[i]);
    }//cout <<endl;
    
    return segtree[0].ans>=0;
}
bool is_happy(int event, int coinsCount, long long coins[]){
    sort(coins,coins+coinsCount);
    for (int i = 0; i < coinsCount; ++i)
    {
        query(0,coins[i],event);
        if(event==-1) update(0,coins[i]+1,mx,-coins[i]);
        else update(0,coins[i]+1,mx,coins[i]);
        //cout <<segtree[0].ans<<endl;
        //cout <<segtree[0].sum<<" ";
    }
    return segtree[0].ans>=0;
}

Compilation message

happiness.cpp: In constructor 'Node::Node()':
happiness.cpp:15:17: warning: 'Node::ans' will be initialized after [-Wreorder]
   15 |     double long ans;
      |                 ^~~
happiness.cpp:14:21: warning:   'long long int Node::l' [-Wreorder]
   14 |     long long lazy, l, r, cnt, tl, tr;
      |                     ^
happiness.cpp:16:5: warning:   when initialized here [-Wreorder]
   16 |     Node(): lazy(0), ans(0), l(-1), r(-1), cnt(0) {}
      |     ^~~~
happiness.cpp: At global scope:
happiness.cpp:11:31: warning: 'A' defined but not used [-Wunused-variable]
   11 | static long long coins[NMAX], A[5];
      |                               ^
happiness.cpp:11:18: warning: 'coins' defined but not used [-Wunused-variable]
   11 | static long long coins[NMAX], A[5];
      |                  ^~~~~
happiness.cpp:10:18: warning: 'M' defined but not used [-Wunused-variable]
   10 | static long long M;
      |                  ^
happiness.cpp:9:15: warning: 'Q' defined but not used [-Wunused-variable]
    9 | static int N, Q;
      |               ^
happiness.cpp:9:12: warning: 'N' defined but not used [-Wunused-variable]
    9 | static int N, Q;
      |            ^
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 106 ms 495188 KB Output is correct
2 Correct 85 ms 495032 KB Output is correct
3 Correct 84 ms 495188 KB Output is correct
4 Correct 82 ms 495188 KB Output is correct
5 Correct 86 ms 495004 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 495188 KB Output is correct
2 Correct 85 ms 495032 KB Output is correct
3 Correct 84 ms 495188 KB Output is correct
4 Correct 82 ms 495188 KB Output is correct
5 Correct 86 ms 495004 KB Output is correct
6 Correct 86 ms 495140 KB Output is correct
7 Correct 85 ms 495096 KB Output is correct
8 Correct 118 ms 495276 KB Output is correct
9 Correct 118 ms 495288 KB Output is correct
10 Correct 113 ms 495188 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 495188 KB Output is correct
2 Correct 85 ms 495032 KB Output is correct
3 Correct 84 ms 495188 KB Output is correct
4 Correct 82 ms 495188 KB Output is correct
5 Correct 86 ms 495004 KB Output is correct
6 Correct 617 ms 496356 KB Output is correct
7 Correct 605 ms 495956 KB Output is correct
8 Correct 608 ms 496160 KB Output is correct
9 Correct 1006 ms 496292 KB Output is correct
10 Correct 959 ms 496208 KB Output is correct
11 Correct 458 ms 495160 KB Output is correct
12 Correct 460 ms 495184 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 495188 KB Output is correct
2 Correct 85 ms 495032 KB Output is correct
3 Correct 84 ms 495188 KB Output is correct
4 Correct 82 ms 495188 KB Output is correct
5 Correct 86 ms 495004 KB Output is correct
6 Correct 86 ms 495140 KB Output is correct
7 Correct 85 ms 495096 KB Output is correct
8 Correct 118 ms 495276 KB Output is correct
9 Correct 118 ms 495288 KB Output is correct
10 Correct 113 ms 495188 KB Output is correct
11 Correct 617 ms 496356 KB Output is correct
12 Correct 605 ms 495956 KB Output is correct
13 Correct 608 ms 496160 KB Output is correct
14 Correct 1006 ms 496292 KB Output is correct
15 Correct 959 ms 496208 KB Output is correct
16 Correct 458 ms 495160 KB Output is correct
17 Correct 460 ms 495184 KB Output is correct
18 Runtime error 737 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -