oj.uz

Submission #797673

# Submission time Handle Problem Language Result Execution time Memory
797673 2023-07-29T18:05:41 Z idiotcomputer Happiness (Balkan15_HAPPINESS) C++11
60 / 100
 1491 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[100*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 125 ms 391576 KB Output is correct
2 Correct 124 ms 391608 KB Output is correct
3 Correct 127 ms 391568 KB Output is correct
4 Correct 145 ms 391616 KB Output is correct
5 Correct 123 ms 391620 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 391576 KB Output is correct
2 Correct 124 ms 391608 KB Output is correct
3 Correct 127 ms 391568 KB Output is correct
4 Correct 145 ms 391616 KB Output is correct
5 Correct 123 ms 391620 KB Output is correct
6 Correct 132 ms 391856 KB Output is correct
7 Correct 128 ms 391688 KB Output is correct
8 Correct 154 ms 392396 KB Output is correct
9 Correct 166 ms 392340 KB Output is correct
10 Correct 155 ms 392324 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 391576 KB Output is correct
2 Correct 124 ms 391608 KB Output is correct
3 Correct 127 ms 391568 KB Output is correct
4 Correct 145 ms 391616 KB Output is correct
5 Correct 123 ms 391620 KB Output is correct
6 Correct 870 ms 397796 KB Output is correct
7 Correct 849 ms 397572 KB Output is correct
8 Correct 849 ms 397664 KB Output is correct
9 Correct 1271 ms 397736 KB Output is correct
10 Correct 1491 ms 400176 KB Output is correct
11 Correct 749 ms 401556 KB Output is correct
12 Correct 736 ms 401416 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 391576 KB Output is correct
2 Correct 124 ms 391608 KB Output is correct
3 Correct 127 ms 391568 KB Output is correct
4 Correct 145 ms 391616 KB Output is correct
5 Correct 123 ms 391620 KB Output is correct
6 Correct 132 ms 391856 KB Output is correct
7 Correct 128 ms 391688 KB Output is correct
8 Correct 154 ms 392396 KB Output is correct
9 Correct 166 ms 392340 KB Output is correct
10 Correct 155 ms 392324 KB Output is correct
11 Correct 870 ms 397796 KB Output is correct
12 Correct 849 ms 397572 KB Output is correct
13 Correct 849 ms 397664 KB Output is correct
14 Correct 1271 ms 397736 KB Output is correct
15 Correct 1491 ms 400176 KB Output is correct
16 Correct 749 ms 401556 KB Output is correct
17 Correct 736 ms 401416 KB Output is correct
18 Correct 1164 ms 397704 KB Output is correct
19 Correct 1162 ms 397580 KB Output is correct
20 Runtime error 1159 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -