oj.uz

Submission #797667

# Submission time Handle Problem Language Result Execution time Memory
797667 2023-07-29T18:00:20 Z idiotcomputer Happiness (Balkan15_HAPPINESS) C++11
60 / 100
 1155 ms 408288 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[50*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 75 ms 195944 KB Output is correct
2 Correct 66 ms 195868 KB Output is correct
3 Correct 67 ms 195916 KB Output is correct
4 Correct 66 ms 195892 KB Output is correct
5 Correct 66 ms 195936 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 195944 KB Output is correct
2 Correct 66 ms 195868 KB Output is correct
3 Correct 67 ms 195916 KB Output is correct
4 Correct 66 ms 195892 KB Output is correct
5 Correct 66 ms 195936 KB Output is correct
6 Correct 72 ms 196144 KB Output is correct
7 Correct 70 ms 196016 KB Output is correct
8 Correct 92 ms 196552 KB Output is correct
9 Correct 94 ms 196552 KB Output is correct
10 Correct 90 ms 196380 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 195944 KB Output is correct
2 Correct 66 ms 195868 KB Output is correct
3 Correct 67 ms 195916 KB Output is correct
4 Correct 66 ms 195892 KB Output is correct
5 Correct 66 ms 195936 KB Output is correct
6 Correct 754 ms 206444 KB Output is correct
7 Correct 711 ms 206576 KB Output is correct
8 Correct 757 ms 206356 KB Output is correct
9 Correct 1155 ms 208192 KB Output is correct
10 Correct 1129 ms 209192 KB Output is correct
11 Correct 576 ms 209780 KB Output is correct
12 Correct 607 ms 209788 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 195944 KB Output is correct
2 Correct 66 ms 195868 KB Output is correct
3 Correct 67 ms 195916 KB Output is correct
4 Correct 66 ms 195892 KB Output is correct
5 Correct 66 ms 195936 KB Output is correct
6 Correct 72 ms 196144 KB Output is correct
7 Correct 70 ms 196016 KB Output is correct
8 Correct 92 ms 196552 KB Output is correct
9 Correct 94 ms 196552 KB Output is correct
10 Correct 90 ms 196380 KB Output is correct
11 Correct 754 ms 206444 KB Output is correct
12 Correct 711 ms 206576 KB Output is correct
13 Correct 757 ms 206356 KB Output is correct
14 Correct 1155 ms 208192 KB Output is correct
15 Correct 1129 ms 209192 KB Output is correct
16 Correct 576 ms 209780 KB Output is correct
17 Correct 607 ms 209788 KB Output is correct
18 Runtime error 700 ms 408288 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -