oj.uz

Submission #797665

# Submission time Handle Problem Language Result Execution time Memory
797665 2023-07-29T17:59:20 Z idiotcomputer Happiness (Balkan15_HAPPINESS) C++11
60 / 100
 1140 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[75*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 110 ms 293740 KB Output is correct
2 Correct 96 ms 293756 KB Output is correct
3 Correct 98 ms 293792 KB Output is correct
4 Correct 96 ms 293732 KB Output is correct
5 Correct 97 ms 293740 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 293740 KB Output is correct
2 Correct 96 ms 293756 KB Output is correct
3 Correct 98 ms 293792 KB Output is correct
4 Correct 96 ms 293732 KB Output is correct
5 Correct 97 ms 293740 KB Output is correct
6 Correct 97 ms 293880 KB Output is correct
7 Correct 100 ms 293840 KB Output is correct
8 Correct 120 ms 294448 KB Output is correct
9 Correct 122 ms 294436 KB Output is correct
10 Correct 122 ms 294196 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 293740 KB Output is correct
2 Correct 96 ms 293756 KB Output is correct
3 Correct 98 ms 293792 KB Output is correct
4 Correct 96 ms 293732 KB Output is correct
5 Correct 97 ms 293740 KB Output is correct
6 Correct 741 ms 304264 KB Output is correct
7 Correct 732 ms 304316 KB Output is correct
8 Correct 755 ms 304424 KB Output is correct
9 Correct 1138 ms 305880 KB Output is correct
10 Correct 1140 ms 307008 KB Output is correct
11 Correct 619 ms 307700 KB Output is correct
12 Correct 603 ms 307612 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 293740 KB Output is correct
2 Correct 96 ms 293756 KB Output is correct
3 Correct 98 ms 293792 KB Output is correct
4 Correct 96 ms 293732 KB Output is correct
5 Correct 97 ms 293740 KB Output is correct
6 Correct 97 ms 293880 KB Output is correct
7 Correct 100 ms 293840 KB Output is correct
8 Correct 120 ms 294448 KB Output is correct
9 Correct 122 ms 294436 KB Output is correct
10 Correct 122 ms 294196 KB Output is correct
11 Correct 741 ms 304264 KB Output is correct
12 Correct 732 ms 304316 KB Output is correct
13 Correct 755 ms 304424 KB Output is correct
14 Correct 1138 ms 305880 KB Output is correct
15 Correct 1140 ms 307008 KB Output is correct
16 Correct 619 ms 307700 KB Output is correct
17 Correct 603 ms 307612 KB Output is correct
18 Runtime error 966 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -