oj.uz

Submission #797663

# Submission time Handle Problem Language Result Execution time Memory
797663 2023-07-29T17:57:44 Z idiotcomputer Happiness (Balkan15_HAPPINESS) C++11
60 / 100
 1203 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[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;
}
 
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 124 ms 391604 KB Output is correct
2 Correct 125 ms 391596 KB Output is correct
3 Correct 124 ms 391608 KB Output is correct
4 Correct 125 ms 391632 KB Output is correct
5 Correct 125 ms 391572 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 391604 KB Output is correct
2 Correct 125 ms 391596 KB Output is correct
3 Correct 124 ms 391608 KB Output is correct
4 Correct 125 ms 391632 KB Output is correct
5 Correct 125 ms 391572 KB Output is correct
6 Correct 126 ms 391648 KB Output is correct
7 Correct 127 ms 391668 KB Output is correct
8 Correct 150 ms 392504 KB Output is correct
9 Correct 149 ms 392508 KB Output is correct
10 Correct 147 ms 392216 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 391604 KB Output is correct
2 Correct 125 ms 391596 KB Output is correct
3 Correct 124 ms 391608 KB Output is correct
4 Correct 125 ms 391632 KB Output is correct
5 Correct 125 ms 391572 KB Output is correct
6 Correct 782 ms 402412 KB Output is correct
7 Correct 748 ms 402372 KB Output is correct
8 Correct 769 ms 402424 KB Output is correct
9 Correct 1191 ms 403960 KB Output is correct
10 Correct 1203 ms 405060 KB Output is correct
11 Correct 638 ms 405928 KB Output is correct
12 Correct 638 ms 405620 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 391604 KB Output is correct
2 Correct 125 ms 391596 KB Output is correct
3 Correct 124 ms 391608 KB Output is correct
4 Correct 125 ms 391632 KB Output is correct
5 Correct 125 ms 391572 KB Output is correct
6 Correct 126 ms 391648 KB Output is correct
7 Correct 127 ms 391668 KB Output is correct
8 Correct 150 ms 392504 KB Output is correct
9 Correct 149 ms 392508 KB Output is correct
10 Correct 147 ms 392216 KB Output is correct
11 Correct 782 ms 402412 KB Output is correct
12 Correct 748 ms 402372 KB Output is correct
13 Correct 769 ms 402424 KB Output is correct
14 Correct 1191 ms 403960 KB Output is correct
15 Correct 1203 ms 405060 KB Output is correct
16 Correct 638 ms 405928 KB Output is correct
17 Correct 638 ms 405620 KB Output is correct
18 Correct 1094 ms 402360 KB Output is correct
19 Correct 1099 ms 402144 KB Output is correct
20 Runtime error 1062 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -