oj.uz

Submission #797688

# Submission time Handle Problem Language Result Execution time Memory
797688 2023-07-29T18:55:31 Z idiotcomputer Happiness (Balkan15_HAPPINESS) C++11
60 / 100
 1353 ms 524288 KB 
#include "happiness.h"
#include <bits/stdc++.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[56*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 76 ms 219408 KB Output is correct
2 Correct 74 ms 219444 KB Output is correct
3 Correct 75 ms 219420 KB Output is correct
4 Correct 77 ms 219408 KB Output is correct
5 Correct 81 ms 219384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 219408 KB Output is correct
2 Correct 74 ms 219444 KB Output is correct
3 Correct 75 ms 219420 KB Output is correct
4 Correct 77 ms 219408 KB Output is correct
5 Correct 81 ms 219384 KB Output is correct
6 Correct 75 ms 219440 KB Output is correct
7 Correct 76 ms 219468 KB Output is correct
8 Correct 102 ms 219968 KB Output is correct
9 Correct 103 ms 219916 KB Output is correct
10 Correct 99 ms 219992 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 219408 KB Output is correct
2 Correct 74 ms 219444 KB Output is correct
3 Correct 75 ms 219420 KB Output is correct
4 Correct 77 ms 219408 KB Output is correct
5 Correct 81 ms 219384 KB Output is correct
6 Correct 782 ms 225128 KB Output is correct
7 Correct 739 ms 225100 KB Output is correct
8 Correct 793 ms 225124 KB Output is correct
9 Correct 1244 ms 225072 KB Output is correct
10 Correct 1353 ms 227764 KB Output is correct
11 Correct 760 ms 228980 KB Output is correct
12 Correct 694 ms 229032 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 219408 KB Output is correct
2 Correct 74 ms 219444 KB Output is correct
3 Correct 75 ms 219420 KB Output is correct
4 Correct 77 ms 219408 KB Output is correct
5 Correct 81 ms 219384 KB Output is correct
6 Correct 75 ms 219440 KB Output is correct
7 Correct 76 ms 219468 KB Output is correct
8 Correct 102 ms 219968 KB Output is correct
9 Correct 103 ms 219916 KB Output is correct
10 Correct 99 ms 219992 KB Output is correct
11 Correct 782 ms 225128 KB Output is correct
12 Correct 739 ms 225100 KB Output is correct
13 Correct 793 ms 225124 KB Output is correct
14 Correct 1244 ms 225072 KB Output is correct
15 Correct 1353 ms 227764 KB Output is correct
16 Correct 760 ms 228980 KB Output is correct
17 Correct 694 ms 229032 KB Output is correct
18 Runtime error 802 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -