oj.uz

Submission #284058

# Submission time Handle Problem Language Result Execution time Memory
284058 2020-08-26T15:36:01 Z NaimSS Happiness (Balkan15_HAPPINESS) C++14
30 / 100
 2000 ms 54756 KB 
#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;

const ll inf = 1e16;
const ll MAX = (1e12) + 10;
struct node{
  node* c[2];
  ll lazy;
  ll mx;
  node(){c[0] = c[1] = nullptr;lazy = mx = 0;}
  void push(ll l , ll r){
    if(!lazy) return ;
    if(l!=r){
      if(!c[0]) c[0] = new node();
      if(!c[1]) c[1] = new node();
      c[0]->lazy += lazy , c[1]->lazy += lazy;
    }
    mx+=lazy;
    lazy=0;
    return ;
  } 
  void pull(ll l, ll r){
    push(l,r); ll mid = (l+r)/2;
    
    if(c[0]) c[0]->push(l, mid);
    if(c[1]) c[1]->push(mid+1, r);
    mx = max(c[0] ? c[0]->mx : 0,c[1] ? c[1]->mx : 0);
  }
  void upd(ll x , ll y , ll v , ll l = 1 , ll r = MAX){
    push(l,r);
    ll mid = (l + r)/2;
    if(x==l && y==r){
      lazy += v; 
      push(l,r);
      return ;
    }
    if(y <= mid){
      if(!c[0]) c[0] = new node();
      c[0]->upd(x,y,v,l,mid);
    }
    else if(x > mid){
      if(!c[1]) c[1] = new node();
      c[1]->upd(x,y,v,mid+1,r);
    }
    else{
      if(!c[0]) c[0] = new node();
      if(!c[1]) c[1] = new node();
      c[0]->upd(x,mid,v,l,mid) , c[1]->upd(mid+1,y,v,mid+1,r);      
    }
    pull(l,r);
  }
  ll qry(ll x , ll y , ll l = 1, ll r = MAX){
    push(l,r);
    ll mid = l + (r-l)/2;
    
    if(x == l && y == r){
      return mx;
    }
    if(y <= mid){
      if(!c[0]) return 0;
      return c[0]->qry(x,y,l,mid);
    }
    else if(x > mid){
      if(!c[1]) return 0;
      return c[1]->qry(x,y,mid+1,r);
    }
    else{
      return max( (c[0] != nullptr ? c[0]->qry(x,mid,l,mid) : 0) , (c[1] != nullptr ? c[1]->qry(mid+1,y,mid+1,r) : 0));
    }
  }
};

node* tree;
ll N;
ll cnt1 = 0;
multiset<ll> S; 


bool ok(){
	ll sum=0;
	for(ll x : S){
		if(x > sum + 1)return 0;
		sum+=x;
	}
	return 1;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	tree = new node();
	tree->upd(1,MAX,-1);

	N = coinsCount;
	for(int i=0;i<N;i++){
		ll val = coins[i];
		if(val == 1){
			cnt1++;
		}
		tree->upd(val+1,MAX,-val);
		tree->upd(val,val,+val);
		S.insert(val);
	}
	ll mx = tree->qry(2,MAX);
	bool OK = ok();
	if((mx <=0 and cnt1>0))assert(OK);
	return OK;
	if(N == 0)return true;
	if( mx <= 0 and cnt1 > 0)return true;
	return false;
}
bool is_happy(int event, int coinsCount, long long coins[]) {
	
	N+=coinsCount*event;
	for(int i=0;i<coinsCount;i++){
			ll val = coins[i];
			ll sla = val;
			if(event == -1)sla = -sla;
			if(event == -1){
				S.erase(S.find(val));
			}else S.insert(val);
			if(val == 1){
				cnt1+=event;
			}
			tree->upd(val+1,MAX,-sla);
			tree->upd(val,val,+sla);
	}
	
	ll mx = tree->qry(2,MAX);	
	bool OK = ok();
	if((mx <=0 and cnt1>0))assert(OK);
	return OK;

	if(N == 0)return true;
	if( mx <=0 and cnt1 > 0)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 1 ms 384 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 16 ms 6016 KB Output is correct
7 Correct 12 ms 6528 KB Output is correct
8 Correct 509 ms 51224 KB Output is correct
9 Correct 511 ms 51732 KB Output is correct
10 Correct 527 ms 49912 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Execution timed out 2074 ms 54756 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 16 ms 6016 KB Output is correct
7 Correct 12 ms 6528 KB Output is correct
8 Correct 509 ms 51224 KB Output is correct
9 Correct 511 ms 51732 KB Output is correct
10 Correct 527 ms 49912 KB Output is correct
11 Execution timed out 2074 ms 54756 KB Time limit exceeded
12 Halted 0 ms 0 KB -