oj.uz

Submission #797674

# Submission time Handle Problem Language Result Execution time Memory
797674 2023-07-29T18:07:04 Z idiotcomputer Happiness (Balkan15_HAPPINESS) C++11
60 / 100
 1371 ms 524288 KB 
#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;


const long long int MAX_V = 1e12; 
const int MAX_Q = 1e5;

struct node {
    long long int tl,tr;
    int l = -1;
    int r = -1;
    long long int sum = 0;
    long long int lazy = 0;
};

node segt[75*MAX_Q];
int cnt = 0;

void cnew(int idx){
    long long int m = (segt[idx].tl + segt[idx].tr)/2;
    if (segt[idx].l == -1){
        segt[idx].l = cnt;
        segt[cnt].tl = segt[idx].tl;
        segt[cnt].tr = m;
        cnt++;
    }
    if (segt[idx].r == -1){
        segt[idx].r = cnt;
        segt[cnt].tl = m+1;
        segt[cnt].tr = segt[idx].tr;
        cnt++;
    }
}

void upd(int idx, long long int tl, long long int tr, long long int v){
    if (segt[idx].tl > tr || segt[idx].tr < tl){
        return;
    }
    if (segt[idx].tl >= tl && segt[idx].tr <= tr){
        segt[idx].lazy += v;
        return;
    }
    cnew(idx);
    int cl = segt[idx].l;
    int cr = segt[idx].r;
    upd(cl,tl,tr,v);
    upd(cr,tl,tr,v);
    segt[idx].sum = min(segt[cl].sum + segt[cl].lazy, segt[cr].sum + segt[cr].lazy);
    return;
}

multiset<long long int> vis;

bool init(int coinsCount, long long maxCoinSize, long long coins[]){
    segt[0].tl = 1;
    segt[0].tr = MAX_V;
    cnt++;
    for (int i =0; i < coinsCount; i++){
        if (coins[i] != MAX_V){
            upd(0,coins[i]+1,MAX_V,coins[i]);
        }
        auto it = vis.lower_bound(coins[i]);
        if (it == vis.end() || (*it) != coins[i]){
            upd(0,coins[i],coins[i],-1*coins[i]);
        }
        vis.insert(coins[i]);
    }
    if (segt[0].sum + segt[0].lazy >= -1){
        return true;
    }
    return false;
}

bool is_happy(int event, int coinsCount, long long coins[]){
    if (event == -1){
        //shopping
        for (int i =0; i < coinsCount; i++){
            upd(0,coins[i]+1,MAX_V,-1*coins[i]);
            vis.erase(vis.find(coins[i]));
            
            auto it = vis.lower_bound(coins[i]);
            if (it == vis.end() || (*it) != coins[i]){
                upd(0,coins[i],coins[i],coins[i]);
            }
        }
    } else {
        //adding
        for (int i =0; i < coinsCount; i++){
            upd(0,coins[i]+1,MAX_V,coins[i]);
            auto it = vis.lower_bound(coins[i]);
            if (it == vis.end() || (*it) != coins[i]){
                upd(0,coins[i],coins[i],-1*coins[i]);
            }
            vis.insert(coins[i]);
        }
    }
    if (segt[0].sum + segt[0].lazy >= -1){
        return true;
    }
    return false;
}

Compilation message

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 95 ms 293808 KB Output is correct
2 Correct 95 ms 293744 KB Output is correct
3 Correct 97 ms 293772 KB Output is correct
4 Correct 96 ms 293820 KB Output is correct
5 Correct 100 ms 293900 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 293808 KB Output is correct
2 Correct 95 ms 293744 KB Output is correct
3 Correct 97 ms 293772 KB Output is correct
4 Correct 96 ms 293820 KB Output is correct
5 Correct 100 ms 293900 KB Output is correct
6 Correct 99 ms 293824 KB Output is correct
7 Correct 98 ms 293844 KB Output is correct
8 Correct 124 ms 294280 KB Output is correct
9 Correct 123 ms 294320 KB Output is correct
10 Correct 121 ms 294348 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 293808 KB Output is correct
2 Correct 95 ms 293744 KB Output is correct
3 Correct 97 ms 293772 KB Output is correct
4 Correct 96 ms 293820 KB Output is correct
5 Correct 100 ms 293900 KB Output is correct
6 Correct 801 ms 299612 KB Output is correct
7 Correct 788 ms 299440 KB Output is correct
8 Correct 793 ms 299456 KB Output is correct
9 Correct 1256 ms 299676 KB Output is correct
10 Correct 1371 ms 302108 KB Output is correct
11 Correct 719 ms 303412 KB Output is correct
12 Correct 715 ms 303428 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 293808 KB Output is correct
2 Correct 95 ms 293744 KB Output is correct
3 Correct 97 ms 293772 KB Output is correct
4 Correct 96 ms 293820 KB Output is correct
5 Correct 100 ms 293900 KB Output is correct
6 Correct 99 ms 293824 KB Output is correct
7 Correct 98 ms 293844 KB Output is correct
8 Correct 124 ms 294280 KB Output is correct
9 Correct 123 ms 294320 KB Output is correct
10 Correct 121 ms 294348 KB Output is correct
11 Correct 801 ms 299612 KB Output is correct
12 Correct 788 ms 299440 KB Output is correct
13 Correct 793 ms 299456 KB Output is correct
14 Correct 1256 ms 299676 KB Output is correct
15 Correct 1371 ms 302108 KB Output is correct
16 Correct 719 ms 303412 KB Output is correct
17 Correct 715 ms 303428 KB Output is correct
18 Runtime error 1035 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -