oj.uz

Submission #797654

# Submission time Handle Problem Language Result Execution time Memory
797654 2023-07-29T17:44:38 Z idiotcomputer Happiness (Balkan15_HAPPINESS) C++11
60 / 100
 2000 ms 409336 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<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 205 ms 391592 KB Output is correct
2 Correct 137 ms 391588 KB Output is correct
3 Correct 150 ms 391688 KB Output is correct
4 Correct 154 ms 391720 KB Output is correct
5 Correct 143 ms 391608 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 391592 KB Output is correct
2 Correct 137 ms 391588 KB Output is correct
3 Correct 150 ms 391688 KB Output is correct
4 Correct 154 ms 391720 KB Output is correct
5 Correct 143 ms 391608 KB Output is correct
6 Correct 129 ms 391756 KB Output is correct
7 Correct 141 ms 391772 KB Output is correct
8 Correct 160 ms 392544 KB Output is correct
9 Correct 153 ms 392448 KB Output is correct
10 Correct 150 ms 392204 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 391592 KB Output is correct
2 Correct 137 ms 391588 KB Output is correct
3 Correct 150 ms 391688 KB Output is correct
4 Correct 154 ms 391720 KB Output is correct
5 Correct 143 ms 391608 KB Output is correct
6 Correct 804 ms 405288 KB Output is correct
7 Correct 844 ms 405252 KB Output is correct
8 Correct 798 ms 405212 KB Output is correct
9 Correct 1197 ms 408136 KB Output is correct
10 Correct 1331 ms 409336 KB Output is correct
11 Correct 650 ms 409232 KB Output is correct
12 Correct 659 ms 409324 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 391592 KB Output is correct
2 Correct 137 ms 391588 KB Output is correct
3 Correct 150 ms 391688 KB Output is correct
4 Correct 154 ms 391720 KB Output is correct
5 Correct 143 ms 391608 KB Output is correct
6 Correct 129 ms 391756 KB Output is correct
7 Correct 141 ms 391772 KB Output is correct
8 Correct 160 ms 392544 KB Output is correct
9 Correct 153 ms 392448 KB Output is correct
10 Correct 150 ms 392204 KB Output is correct
11 Correct 804 ms 405288 KB Output is correct
12 Correct 844 ms 405252 KB Output is correct
13 Correct 798 ms 405212 KB Output is correct
14 Correct 1197 ms 408136 KB Output is correct
15 Correct 1331 ms 409336 KB Output is correct
16 Correct 650 ms 409232 KB Output is correct
17 Correct 659 ms 409324 KB Output is correct
18 Execution timed out 2863 ms 402040 KB Time limit exceeded
19 Halted 0 ms 0 KB -