oj.uz

답안 #887611

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
887611 2023-12-14T20:22:33 Z MarwenElarbi Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 524288 KB 
#include <bits/stdc++.h>
#include "happiness.h"
#include <stdio.h>
#include <stdlib.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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{
    int64_t 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,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:12:31: warning: 'A' defined but not used [-Wunused-variable]
   12 | static long long coins[NMAX], A[5];
      |                               ^
happiness.cpp:12:18: warning: 'coins' defined but not used [-Wunused-variable]
   12 | static long long coins[NMAX], A[5];
      |                  ^~~~~
happiness.cpp:11:18: warning: 'M' defined but not used [-Wunused-variable]
   11 | static long long M;
      |                  ^
happiness.cpp:10:15: warning: 'Q' defined but not used [-Wunused-variable]
   10 | static int N, Q;
      |               ^
happiness.cpp:10:12: warning: 'N' defined but not used [-Wunused-variable]
   10 | 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

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 433492 KB Output is correct
2 Correct 53 ms 433540 KB Output is correct
3 Correct 52 ms 433380 KB Output is correct
4 Correct 52 ms 433492 KB Output is correct
5 Correct 58 ms 433484 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 433492 KB Output is correct
2 Correct 53 ms 433540 KB Output is correct
3 Correct 52 ms 433380 KB Output is correct
4 Correct 52 ms 433492 KB Output is correct
5 Correct 58 ms 433484 KB Output is correct
6 Correct 55 ms 433492 KB Output is correct
7 Correct 58 ms 433476 KB Output is correct
8 Correct 82 ms 433492 KB Output is correct
9 Correct 88 ms 433328 KB Output is correct
10 Correct 77 ms 433336 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 433492 KB Output is correct
2 Correct 53 ms 433540 KB Output is correct
3 Correct 52 ms 433380 KB Output is correct
4 Correct 52 ms 433492 KB Output is correct
5 Correct 58 ms 433484 KB Output is correct
6 Correct 479 ms 434516 KB Output is correct
7 Correct 466 ms 434308 KB Output is correct
8 Correct 482 ms 434332 KB Output is correct
9 Correct 785 ms 434264 KB Output is correct
10 Correct 779 ms 434260 KB Output is correct
11 Correct 346 ms 433752 KB Output is correct
12 Correct 350 ms 433744 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 433492 KB Output is correct
2 Correct 53 ms 433540 KB Output is correct
3 Correct 52 ms 433380 KB Output is correct
4 Correct 52 ms 433492 KB Output is correct
5 Correct 58 ms 433484 KB Output is correct
6 Correct 55 ms 433492 KB Output is correct
7 Correct 58 ms 433476 KB Output is correct
8 Correct 82 ms 433492 KB Output is correct
9 Correct 88 ms 433328 KB Output is correct
10 Correct 77 ms 433336 KB Output is correct
11 Correct 479 ms 434516 KB Output is correct
12 Correct 466 ms 434308 KB Output is correct
13 Correct 482 ms 434332 KB Output is correct
14 Correct 785 ms 434264 KB Output is correct
15 Correct 779 ms 434260 KB Output is correct
16 Correct 346 ms 433752 KB Output is correct
17 Correct 350 ms 433744 KB Output is correct
18 Execution timed out 2767 ms 524288 KB Time limit exceeded
19 Halted 0 ms 0 KB -