oj.uz

답안 #887596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
887596 2023-12-14T19:56:46 Z MarwenElarbi Happiness (Balkan15_HAPPINESS) C++17
0 / 100
 7 ms 45660 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[NMAX*4];
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;
    }
    int 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);
    int 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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 45660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 45660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 45660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 45660 KB Output isn't correct
2 Halted 0 ms 0 KB -