oj.uz

Submission #887603

# Submission time Handle Problem Language Result Execution time Memory
887603 2023-12-14T20:10:57 Z MarwenElarbi Happiness (Balkan15_HAPPINESS) C++17
40 / 100
 804 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, 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,int left,int 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,int 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 56 ms 433492 KB Output is correct
2 Correct 55 ms 433380 KB Output is correct
3 Correct 53 ms 433548 KB Output is correct
4 Correct 53 ms 433488 KB Output is correct
5 Correct 53 ms 433488 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 433492 KB Output is correct
2 Correct 55 ms 433380 KB Output is correct
3 Correct 53 ms 433548 KB Output is correct
4 Correct 53 ms 433488 KB Output is correct
5 Correct 53 ms 433488 KB Output is correct
6 Runtime error 120 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 433492 KB Output is correct
2 Correct 55 ms 433380 KB Output is correct
3 Correct 53 ms 433548 KB Output is correct
4 Correct 53 ms 433488 KB Output is correct
5 Correct 53 ms 433488 KB Output is correct
6 Correct 489 ms 434256 KB Output is correct
7 Correct 482 ms 434268 KB Output is correct
8 Correct 504 ms 434252 KB Output is correct
9 Correct 804 ms 434140 KB Output is correct
10 Correct 777 ms 434260 KB Output is correct
11 Correct 360 ms 434044 KB Output is correct
12 Correct 410 ms 433640 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 433492 KB Output is correct
2 Correct 55 ms 433380 KB Output is correct
3 Correct 53 ms 433548 KB Output is correct
4 Correct 53 ms 433488 KB Output is correct
5 Correct 53 ms 433488 KB Output is correct
6 Runtime error 120 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -