oj.uz

Submission #501165

# Submission time Handle Problem Language Result Execution time Memory
501165 2022-01-02T13:50:35 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 365308 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---------------------------------

ll N;
ll ind=0;

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

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

	void extend()
	{
		if(left==-1)
		{
			left=++ind;
			right=++ind;
		}
	}
};

Node T[15'000'000];

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

void _update(ll ind,ll st,ll ed,ll l,ll r,ll val)
{
	if(st>ed or st>r or ed<l)
	{
		return;
	}
	if(st>=l and ed<=r)
	{
		T[ind].val+=val;
		T[ind].lazy+=val;
		return;
	}
	ll mid=(st+ed)>>1;
	T[ind].extend();
	_update(T[ind].left,st,mid,l,r,val);
	_update(T[ind].right,mid+1,ed,l,r,val);
	T[ind].val=combine(T[T[ind].left].val,T[T[ind].right].val)+T[ind].lazy;
}

ll _query(ll ind,ll st,ll ed,ll l,ll r)
{
	if(st>ed or st>r or ed<l)
	{
		return inf;
	}
	if(st>=l and ed<=r)
	{
		return T[ind].val;
	}
	ll mid=(st+ed)>>1;
	T[ind].extend();
	return combine(_query(T[ind].left,st,mid,l,r),_query(T[ind].right,mid+1,ed,l,r))+T[ind].lazy;
}

void init(ll n)
{
	ind=0;
	N=n;
}

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

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

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

bool init(int coinsCount,long long maxCoinSize,long long coins[])
{
	MX=1ll<<40;
	init(MX+100);
	update(0,MX,1);
	forn(i,0,coinsCount)
	{
		if(!cnt.count(coins[i]))
		{
			update(coins[i],coins[i],-coins[i]);
		}
		update(coins[i]+1,MX,coins[i]);
		cnt[coins[i]]++;
	}
	if(cnt.empty())
	{
		return true;
	}
	return (T[0].val+T[0].lazy>=0);
}

bool is_happy(int event,int coinsCount,long long coins[])
{
	if(event==1)
	{
		forn(i,0,coinsCount)
		{
			if(!cnt.count(coins[i]))
			{
				update(coins[i],coins[i],-coins[i]);
			}
			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]))
			{
				update(coins[i],coins[i],coins[i]);
			}
			update(coins[i]+1,MX,-coins[i]);
		}
	}
	if(cnt.empty())
	{
		return true;
	}
	return (T[0].val+T[0].lazy>=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 137 ms 352520 KB Output is correct
2 Correct 146 ms 352444 KB Output is correct
3 Correct 137 ms 352520 KB Output is correct
4 Correct 134 ms 352424 KB Output is correct
5 Correct 136 ms 352596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 352520 KB Output is correct
2 Correct 146 ms 352444 KB Output is correct
3 Correct 137 ms 352520 KB Output is correct
4 Correct 134 ms 352424 KB Output is correct
5 Correct 136 ms 352596 KB Output is correct
6 Correct 170 ms 352580 KB Output is correct
7 Correct 140 ms 352616 KB Output is correct
8 Correct 177 ms 353352 KB Output is correct
9 Correct 173 ms 353400 KB Output is correct
10 Correct 169 ms 353288 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 352520 KB Output is correct
2 Correct 146 ms 352444 KB Output is correct
3 Correct 137 ms 352520 KB Output is correct
4 Correct 134 ms 352424 KB Output is correct
5 Correct 136 ms 352596 KB Output is correct
6 Correct 1102 ms 359948 KB Output is correct
7 Correct 1038 ms 359876 KB Output is correct
8 Correct 1111 ms 359780 KB Output is correct
9 Correct 1663 ms 359768 KB Output is correct
10 Correct 1802 ms 362656 KB Output is correct
11 Correct 1091 ms 365308 KB Output is correct
12 Correct 1089 ms 365196 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 352520 KB Output is correct
2 Correct 146 ms 352444 KB Output is correct
3 Correct 137 ms 352520 KB Output is correct
4 Correct 134 ms 352424 KB Output is correct
5 Correct 136 ms 352596 KB Output is correct
6 Correct 170 ms 352580 KB Output is correct
7 Correct 140 ms 352616 KB Output is correct
8 Correct 177 ms 353352 KB Output is correct
9 Correct 173 ms 353400 KB Output is correct
10 Correct 169 ms 353288 KB Output is correct
11 Correct 1102 ms 359948 KB Output is correct
12 Correct 1038 ms 359876 KB Output is correct
13 Correct 1111 ms 359780 KB Output is correct
14 Correct 1663 ms 359768 KB Output is correct
15 Correct 1802 ms 362656 KB Output is correct
16 Correct 1091 ms 365308 KB Output is correct
17 Correct 1089 ms 365196 KB Output is correct
18 Correct 1377 ms 359868 KB Output is correct
19 Correct 1326 ms 359952 KB Output is correct
20 Execution timed out 2028 ms 361184 KB Time limit exceeded
21 Halted 0 ms 0 KB -