제출 #887608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887608		MarwenElarbi	Happiness (Balkan15_HAPPINESS)	C++17	60 / 100	1006 ms	524288 KiB

happiness

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40