oj.uz

Submission #797661

# Submission time Handle Problem Language Result Execution time Memory
797661 2023-07-29T17:56:14 Z idiotcomputer Happiness (Balkan15_HAPPINESS) C++11
60 / 100
 1405 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[125*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;
}

unordered_map<long long int,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]);
        }
        vis[coins[i]]+=1;
        if (vis[coins[i]] == 1){
            upd(0,coins[i],coins[i],-1*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[coins[i]] -= 1;
            if (vis[coins[i]] == 0){
                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]);
            vis[coins[i]] += 1;
            if (vis[coins[i]] == 1){
                upd(0,coins[i],coins[i],-1*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 295 ms 489500 KB Output is correct
2 Correct 200 ms 489528 KB Output is correct
3 Correct 183 ms 489464 KB Output is correct
4 Correct 172 ms 489556 KB Output is correct
5 Correct 173 ms 489532 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 489500 KB Output is correct
2 Correct 200 ms 489528 KB Output is correct
3 Correct 183 ms 489464 KB Output is correct
4 Correct 172 ms 489556 KB Output is correct
5 Correct 173 ms 489532 KB Output is correct
6 Correct 183 ms 489512 KB Output is correct
7 Correct 215 ms 489508 KB Output is correct
8 Correct 203 ms 490372 KB Output is correct
9 Correct 204 ms 490424 KB Output is correct
10 Correct 197 ms 490176 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 489500 KB Output is correct
2 Correct 200 ms 489528 KB Output is correct
3 Correct 183 ms 489464 KB Output is correct
4 Correct 172 ms 489556 KB Output is correct
5 Correct 173 ms 489532 KB Output is correct
6 Correct 835 ms 503136 KB Output is correct
7 Correct 833 ms 503132 KB Output is correct
8 Correct 818 ms 503056 KB Output is correct
9 Correct 1242 ms 506044 KB Output is correct
10 Correct 1272 ms 507260 KB Output is correct
11 Correct 687 ms 507024 KB Output is correct
12 Correct 694 ms 507268 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 489500 KB Output is correct
2 Correct 200 ms 489528 KB Output is correct
3 Correct 183 ms 489464 KB Output is correct
4 Correct 172 ms 489556 KB Output is correct
5 Correct 173 ms 489532 KB Output is correct
6 Correct 183 ms 489512 KB Output is correct
7 Correct 215 ms 489508 KB Output is correct
8 Correct 203 ms 490372 KB Output is correct
9 Correct 204 ms 490424 KB Output is correct
10 Correct 197 ms 490176 KB Output is correct
11 Correct 835 ms 503136 KB Output is correct
12 Correct 833 ms 503132 KB Output is correct
13 Correct 818 ms 503056 KB Output is correct
14 Correct 1242 ms 506044 KB Output is correct
15 Correct 1272 ms 507260 KB Output is correct
16 Correct 687 ms 507024 KB Output is correct
17 Correct 694 ms 507268 KB Output is correct
18 Correct 1182 ms 504980 KB Output is correct
19 Correct 1191 ms 505356 KB Output is correct
20 Runtime error 1405 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -