oj.uz

Submission #531080

# Submission time Handle Problem Language Result Execution time Memory
531080 2022-02-27T17:33:33 Z Evang Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 248844 KB 
#include <bits/extc++.h>
#include "happiness.h"
using namespace std;
using namespace __gnu_pbds;

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb(x) push_back(x)
#define eb(args...) emplace_back(args)
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


struct node {
  ll x=0, sum=0;
  node *left=nullptr, *right=nullptr;
  node *l() {
    if(left==nullptr)
      left = new node;
    return left;
  }
  node *r(){
    if(right==nullptr)
      right = new node;
    return right;
  }
};
static node *root = new node;

static void upd(ll a, int d){
  ll l = 1, r = 1ll << 40;
  node *v = root;
  vc<node *> anc;
  while(l<r){
    anc.pb(v);
    ll im = (l+r)/2;
    if(a <= im){
      v = v->l();
      r = im;
    }else{
      v = v->r();
      l = im+1;
    }
  }

  v->sum += a*d;
  if(v->sum>0)
    v->x = a-1;
  else
    v->x = 0;
  while(!anc.empty()){
    node *u = anc.back();
    anc.pop_back();
    u->x = max({0ll, u->l()->x, u->r()->x - u->l()->sum});
    u->sum = u->l()->sum + u->r()->sum;
    if(u->sum == 0){
      assert(u->x == 0);
      assert(u->left->sum==0);
      assert(u->right->sum==0);
      delete u->left;
      delete u->right;
      u->left = nullptr;
      u->right = nullptr;
    }
  }
}

bool happy(){
  return root->x == 0;
}

bool init(int n, ll _, ll a[]){
  for(int i = 0; i < n; ++i)
    upd(a[i], 1);
  return happy();
}

bool is_happy(int d, int n, ll a[]){
  for(int i = 0; i < n; ++i)
    upd(a[i], d);
  return happy();
}

#ifdef _DEBUG
signed main(){
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);

  ll a[] = {4, 8, 1, 2, 16};
  cout << init(5, 100, a) << el;
  ll b[] = {2, 8};
  cout << is_happy(-1, 2, b) << el;
  ll c[] = {7, 9, 2};
  cout << is_happy(1, 3, c) << el;
}
#endif

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 0 ms 204 KB Output is correct
2 Correct 1 ms 280 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 280 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 5 ms 3148 KB Output is correct
7 Correct 5 ms 3136 KB Output is correct
8 Correct 40 ms 25680 KB Output is correct
9 Correct 39 ms 25644 KB Output is correct
10 Correct 35 ms 25632 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 280 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 603 ms 37556 KB Output is correct
7 Correct 549 ms 37436 KB Output is correct
8 Correct 545 ms 37428 KB Output is correct
9 Correct 1064 ms 38796 KB Output is correct
10 Correct 881 ms 48668 KB Output is correct
11 Correct 355 ms 36936 KB Output is correct
12 Correct 377 ms 37292 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 280 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 5 ms 3148 KB Output is correct
7 Correct 5 ms 3136 KB Output is correct
8 Correct 40 ms 25680 KB Output is correct
9 Correct 39 ms 25644 KB Output is correct
10 Correct 35 ms 25632 KB Output is correct
11 Correct 603 ms 37556 KB Output is correct
12 Correct 549 ms 37436 KB Output is correct
13 Correct 545 ms 37428 KB Output is correct
14 Correct 1064 ms 38796 KB Output is correct
15 Correct 881 ms 48668 KB Output is correct
16 Correct 355 ms 36936 KB Output is correct
17 Correct 377 ms 37292 KB Output is correct
18 Correct 1370 ms 226208 KB Output is correct
19 Correct 1300 ms 226108 KB Output is correct
20 Execution timed out 2005 ms 248844 KB Time limit exceeded
21 Halted 0 ms 0 KB -