oj.uz

Submission #887606

# Submission time Handle Problem Language Result Execution time Memory
887606 2023-12-14T20:12:38 Z MarwenElarbi Happiness (Balkan15_HAPPINESS) C++17
40 / 100
 795 ms 434672 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, ans, l, r, cnt, tl, tr;
    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,int 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: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 55 ms 433492 KB Output is correct
2 Correct 54 ms 433536 KB Output is correct
3 Correct 54 ms 433492 KB Output is correct
4 Correct 53 ms 433492 KB Output is correct
5 Correct 55 ms 433492 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 433492 KB Output is correct
2 Correct 54 ms 433536 KB Output is correct
3 Correct 54 ms 433492 KB Output is correct
4 Correct 53 ms 433492 KB Output is correct
5 Correct 55 ms 433492 KB Output is correct
6 Incorrect 56 ms 433488 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 433492 KB Output is correct
2 Correct 54 ms 433536 KB Output is correct
3 Correct 54 ms 433492 KB Output is correct
4 Correct 53 ms 433492 KB Output is correct
5 Correct 55 ms 433492 KB Output is correct
6 Correct 509 ms 434348 KB Output is correct
7 Correct 483 ms 434344 KB Output is correct
8 Correct 513 ms 434260 KB Output is correct
9 Correct 792 ms 434672 KB Output is correct
10 Correct 795 ms 434420 KB Output is correct
11 Correct 351 ms 434164 KB Output is correct
12 Correct 354 ms 433724 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 433492 KB Output is correct
2 Correct 54 ms 433536 KB Output is correct
3 Correct 54 ms 433492 KB Output is correct
4 Correct 53 ms 433492 KB Output is correct
5 Correct 55 ms 433492 KB Output is correct
6 Incorrect 56 ms 433488 KB Output isn't correct
7 Halted 0 ms 0 KB -