oj.uz

Submission #797687

# Submission time Handle Problem Language Result Execution time Memory
797687 2023-07-29T18:54:30 Z idiotcomputer Happiness (Balkan15_HAPPINESS) C++11
60 / 100
 1354 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[62*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 94 ms 242916 KB Output is correct
2 Correct 88 ms 242936 KB Output is correct
3 Correct 82 ms 242872 KB Output is correct
4 Correct 81 ms 242844 KB Output is correct
5 Correct 82 ms 242920 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 242916 KB Output is correct
2 Correct 88 ms 242936 KB Output is correct
3 Correct 82 ms 242872 KB Output is correct
4 Correct 81 ms 242844 KB Output is correct
5 Correct 82 ms 242920 KB Output is correct
6 Correct 86 ms 242960 KB Output is correct
7 Correct 84 ms 242932 KB Output is correct
8 Correct 114 ms 243580 KB Output is correct
9 Correct 116 ms 243664 KB Output is correct
10 Correct 107 ms 243600 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 242916 KB Output is correct
2 Correct 88 ms 242936 KB Output is correct
3 Correct 82 ms 242872 KB Output is correct
4 Correct 81 ms 242844 KB Output is correct
5 Correct 82 ms 242920 KB Output is correct
6 Correct 796 ms 249764 KB Output is correct
7 Correct 774 ms 249736 KB Output is correct
8 Correct 856 ms 249712 KB Output is correct
9 Correct 1217 ms 249756 KB Output is correct
10 Correct 1354 ms 252276 KB Output is correct
11 Correct 685 ms 253496 KB Output is correct
12 Correct 698 ms 253540 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 242916 KB Output is correct
2 Correct 88 ms 242936 KB Output is correct
3 Correct 82 ms 242872 KB Output is correct
4 Correct 81 ms 242844 KB Output is correct
5 Correct 82 ms 242920 KB Output is correct
6 Correct 86 ms 242960 KB Output is correct
7 Correct 84 ms 242932 KB Output is correct
8 Correct 114 ms 243580 KB Output is correct
9 Correct 116 ms 243664 KB Output is correct
10 Correct 107 ms 243600 KB Output is correct
11 Correct 796 ms 249764 KB Output is correct
12 Correct 774 ms 249736 KB Output is correct
13 Correct 856 ms 249712 KB Output is correct
14 Correct 1217 ms 249756 KB Output is correct
15 Correct 1354 ms 252276 KB Output is correct
16 Correct 685 ms 253496 KB Output is correct
17 Correct 698 ms 253540 KB Output is correct
18 Runtime error 889 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -