oj.uz

Submission #797689

# Submission time Handle Problem Language Result Execution time Memory
797689 2023-07-29T18:56:55 Z idiotcomputer Happiness (Balkan15_HAPPINESS) C++11
60 / 100
 1474 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[53*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 207640 KB Output is correct
2 Correct 75 ms 207640 KB Output is correct
3 Correct 71 ms 207672 KB Output is correct
4 Correct 70 ms 207652 KB Output is correct
5 Correct 71 ms 207632 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 207640 KB Output is correct
2 Correct 75 ms 207640 KB Output is correct
3 Correct 71 ms 207672 KB Output is correct
4 Correct 70 ms 207652 KB Output is correct
5 Correct 71 ms 207632 KB Output is correct
6 Correct 73 ms 207724 KB Output is correct
7 Correct 71 ms 207664 KB Output is correct
8 Correct 101 ms 208176 KB Output is correct
9 Correct 98 ms 208212 KB Output is correct
10 Correct 94 ms 208184 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 207640 KB Output is correct
2 Correct 75 ms 207640 KB Output is correct
3 Correct 71 ms 207672 KB Output is correct
4 Correct 70 ms 207652 KB Output is correct
5 Correct 71 ms 207632 KB Output is correct
6 Correct 773 ms 213332 KB Output is correct
7 Correct 781 ms 213392 KB Output is correct
8 Correct 849 ms 213304 KB Output is correct
9 Correct 1421 ms 213360 KB Output is correct
10 Correct 1474 ms 215964 KB Output is correct
11 Correct 766 ms 217312 KB Output is correct
12 Correct 709 ms 217308 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 207640 KB Output is correct
2 Correct 75 ms 207640 KB Output is correct
3 Correct 71 ms 207672 KB Output is correct
4 Correct 70 ms 207652 KB Output is correct
5 Correct 71 ms 207632 KB Output is correct
6 Correct 73 ms 207724 KB Output is correct
7 Correct 71 ms 207664 KB Output is correct
8 Correct 101 ms 208176 KB Output is correct
9 Correct 98 ms 208212 KB Output is correct
10 Correct 94 ms 208184 KB Output is correct
11 Correct 773 ms 213332 KB Output is correct
12 Correct 781 ms 213392 KB Output is correct
13 Correct 849 ms 213304 KB Output is correct
14 Correct 1421 ms 213360 KB Output is correct
15 Correct 1474 ms 215964 KB Output is correct
16 Correct 766 ms 217312 KB Output is correct
17 Correct 709 ms 217308 KB Output is correct
18 Runtime error 782 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -