oj.uz

Submission #501046

# Submission time Handle Problem Language Result Execution time Memory
501046 2022-01-02T09:43:26 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1795 ms 524292 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include "happiness.h"

using namespace std;
using namespace __gnu_pbds; 

#define ff              first
#define ss              second
#define ll              int64_t
#define ld              long double
#define nl              cout<<"\n"
#define all(v)          v.begin(),v.end()
#define mset(a,v)       memset((a),(v),sizeof(a))
#define forn(i,a,b)     for(int64_t i=int64_t(a);i<int64_t(b);++i)
#define forb(i,a,b)     for(int64_t i=int64_t(a);i>=int64_t(b);--i)
#define fastio()        ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define mod         1'000'000'007
#define mod2        998'244'353 
#define inf         1'000'000'000'000'007
#define pi          3.14159265358979323846

template<class key,class cmp=std::less<key>>
using ordered_set=tree<key,null_type,cmp,rb_tree_tag,tree_order_statistics_node_update>;

template<class L,class R> ostream& operator<<(ostream& out,pair<L,R> &p)        {return out<<"("<<p.ff<<", "<<p.ss<<")";}
template<class T> ostream& operator<<(ostream& out,vector<T> &v)                {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,deque<T> &v)                 {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,set<T> &s)                   {out<<"{";for(auto it=s.begin();it!=s.end();++it){if(it!=s.begin())out<<", ";out<<*it;}return out<<"}";}
template<class L,class R> ostream& operator<<(ostream& out,map<L,R> &m)         {out<<"{";for(auto it=m.begin();it!=m.end();++it){if(it!=m.begin())out<<", ";out<<*it;}return out<<"}";}

void dbg_out() {cerr<<"]\n";}
template<typename Head,typename... Tail> 
void dbg_out(Head H,Tail... T) {cerr<<H;if(sizeof...(Tail))cerr<<", ";dbg_out(T...);}
#ifdef LOCAL
	#define dbg(...) cerr<<"["<<#__VA_ARGS__<<"] = [",dbg_out(__VA_ARGS__)
#else
	#define dbg(...)
#endif

//---------------------------------mars4---------------------------------

class DynamicSegtree
{
	ll N;

	struct Node
	{
		Node *left;
		Node *right;
		ll val;
		ll lazy;

		Node(): left(NULL), right(NULL), val(0), lazy(0) {}

		void extend()
		{
			if(left==NULL)
			{
				left=new Node();
				right=new Node();
			}
		}
	};

	void _push(Node *cur,ll st,ll ed,ll val)
	{
		if(st!=ed)
		{
			cur->extend();
			cur->left->lazy+=val;
			cur->right->lazy+=val;
		}
	}

	ll combine(ll a,ll b)
	{
		return min(a,b);
	}

	void _update(Node *cur,ll st,ll ed,ll l,ll r,ll val)
	{
		if(cur->lazy)
		{
			cur->val+=cur->lazy;
			_push(cur,st,ed,cur->lazy);
			cur->lazy=0;
		}
		if(st>ed or st>r or ed<l)
		{
			return;
		}
		if(st>=l and ed<=r)
		{
			cur->val+=val;
			_push(cur,st,ed,val);
			return;
		}
		ll mid=(st+ed)>>1;
		cur->extend();
		_update(cur->left,st,mid,l,r,val);
		_update(cur->right,mid+1,ed,l,r,val);
		cur->val=combine(cur->left->val,cur->right->val);
	}

	ll _query(Node *cur,ll st,ll ed,ll l,ll r)
	{
		if(cur->lazy)
		{
			cur->val+=cur->lazy;
			_push(cur,st,ed,cur->lazy);
			cur->lazy=0;
		}
		if(st>ed or st>r or ed<l)
		{
			return 0;
		}
		if(st>=l and ed<=r)
		{
			return cur->val;
		}
		ll mid=(st+ed)>>1;
		cur->extend();
		return combine(_query(cur->left,st,mid,l,r),_query(cur->right,mid+1,ed,l,r));
	}

	public:
	Node *root;

	void init(ll n)
	{
		root=new Node();
		N=n;
	}

	void update(ll l,ll r,ll val)
	{
		_update(root,0,N-1,l,r,val);
	}

	ll query(ll l,ll r)
	{
		return _query(root,0,N-1,l,r);
	}
};

DynamicSegtree ds;
map<ll,ll> cnt;
ll MX=0;

bool init(int coinsCount,long long maxCoinSize,long long coins[])
{
	MX=maxCoinSize;
	ds.init(maxCoinSize+mod);
	ds.update(0,MX,1);
	forn(i,0,coinsCount)
	{
		if(!cnt.count(coins[i]))
		{
			ds.update(coins[i],coins[i],-coins[i]);
		}
		ds.update(coins[i]+1,MX,coins[i]);
		cnt[coins[i]]++;
	}
	if(cnt.empty())
	{
		return true;
	}
	return (ds.query(0,cnt.rbegin()->ff)>=0);
}

bool is_happy(int event,int coinsCount,long long coins[])
{
	if(event==1)
	{
		forn(i,0,coinsCount)
		{
			if(!cnt.count(coins[i]))
			{
				ds.update(coins[i],coins[i],-coins[i]);
			}
			ds.update(coins[i]+1,MX,coins[i]);
			cnt[coins[i]]++;
		}
	}
	else
	{
		forn(i,0,coinsCount)
		{
			cnt[coins[i]]--;
			if(cnt[coins[i]]==0)
			{
				cnt.erase(coins[i]);
			}
			if(!cnt.count(coins[i]))
			{
				ds.update(coins[i],coins[i],coins[i]);
			}
			ds.update(coins[i]+1,MX,-coins[i]);
		}
	}
	if(cnt.empty())
	{
		return true;
	}
	return (ds.query(0,cnt.rbegin()->ff)>=0);
}

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 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 296 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 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 9 ms 6092 KB Output is correct
7 Correct 9 ms 6588 KB Output is correct
8 Correct 83 ms 51180 KB Output is correct
9 Correct 84 ms 51576 KB Output is correct
10 Correct 75 ms 49924 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1071 ms 71024 KB Output is correct
7 Correct 1020 ms 70432 KB Output is correct
8 Correct 1020 ms 71272 KB Output is correct
9 Correct 1643 ms 84732 KB Output is correct
10 Correct 1795 ms 93216 KB Output is correct
11 Correct 668 ms 48196 KB Output is correct
12 Correct 668 ms 48296 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 9 ms 6092 KB Output is correct
7 Correct 9 ms 6588 KB Output is correct
8 Correct 83 ms 51180 KB Output is correct
9 Correct 84 ms 51576 KB Output is correct
10 Correct 75 ms 49924 KB Output is correct
11 Correct 1071 ms 71024 KB Output is correct
12 Correct 1020 ms 70432 KB Output is correct
13 Correct 1020 ms 71272 KB Output is correct
14 Correct 1643 ms 84732 KB Output is correct
15 Correct 1795 ms 93216 KB Output is correct
16 Correct 668 ms 48196 KB Output is correct
17 Correct 668 ms 48296 KB Output is correct
18 Runtime error 1398 ms 524292 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -