oj.uz

Submission #887616

# Submission time Handle Problem Language Result Execution time Memory
887616 2023-12-14T20:26:02 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
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
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 expand(int pos){
    if(segtree[pos].lazy!=0){
        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;
        }
        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;
    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;
    }
    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;
    }
    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;
    }
    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[]){
    optimise;
    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

# Verdict Execution time Memory Grader output
1 Correct 75 ms 433488 KB Output is correct
2 Correct 57 ms 433492 KB Output is correct
3 Correct 55 ms 433488 KB Output is correct
4 Correct 56 ms 433492 KB Output is correct
5 Correct 58 ms 433416 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 433488 KB Output is correct
2 Correct 57 ms 433492 KB Output is correct
3 Correct 55 ms 433488 KB Output is correct
4 Correct 56 ms 433492 KB Output is correct
5 Correct 58 ms 433416 KB Output is correct
6 Correct 57 ms 433372 KB Output is correct
7 Correct 61 ms 433488 KB Output is correct
8 Correct 84 ms 433500 KB Output is correct
9 Correct 82 ms 433492 KB Output is correct
10 Correct 77 ms 433488 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 433488 KB Output is correct
2 Correct 57 ms 433492 KB Output is correct
3 Correct 55 ms 433488 KB Output is correct
4 Correct 56 ms 433492 KB Output is correct
5 Correct 58 ms 433416 KB Output is correct
6 Correct 494 ms 434256 KB Output is correct
7 Correct 470 ms 434256 KB Output is correct
8 Correct 486 ms 434344 KB Output is correct
9 Correct 768 ms 434248 KB Output is correct
10 Correct 793 ms 434328 KB Output is correct
11 Correct 369 ms 433900 KB Output is correct
12 Correct 348 ms 433632 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 433488 KB Output is correct
2 Correct 57 ms 433492 KB Output is correct
3 Correct 55 ms 433488 KB Output is correct
4 Correct 56 ms 433492 KB Output is correct
5 Correct 58 ms 433416 KB Output is correct
6 Correct 57 ms 433372 KB Output is correct
7 Correct 61 ms 433488 KB Output is correct
8 Correct 84 ms 433500 KB Output is correct
9 Correct 82 ms 433492 KB Output is correct
10 Correct 77 ms 433488 KB Output is correct
11 Correct 494 ms 434256 KB Output is correct
12 Correct 470 ms 434256 KB Output is correct
13 Correct 486 ms 434344 KB Output is correct
14 Correct 768 ms 434248 KB Output is correct
15 Correct 793 ms 434328 KB Output is correct
16 Correct 369 ms 433900 KB Output is correct
17 Correct 348 ms 433632 KB Output is correct
18 Execution timed out 2699 ms 524288 KB Time limit exceeded
19 Halted 0 ms 0 KB -