oj.uz

Submission #501062

# Submission time Handle Problem Language Result Execution time Memory
501062 2022-01-02T10:14:50 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 524288 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;
		}
	}
};

vector<Node> T(16'000'000);

void _push(ll ind,ll st,ll ed,ll val)
{
	if(st!=ed)
	{
		T[ind].extend();
		T[T[ind].left].lazy+=val;
		T[T[ind].right].lazy+=val;
	}
}

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(T[ind].lazy)
	{
		T[ind].val+=T[ind].lazy;
		_push(ind,st,ed,T[ind].lazy);
		T[ind].lazy=0;
	}
	if(st>ed or st>r or ed<l)
	{
		return;
	}
	if(st>=l and ed<=r)
	{
		T[ind].val+=val;
		_push(ind,st,ed,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);
}

ll _query(ll ind,ll st,ll ed,ll l,ll r)
{
	if(T[ind].lazy)
	{
		T[ind].val+=T[ind].lazy;
		_push(ind,st,ed,T[ind].lazy);
		T[ind].lazy=0;
	}
	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));
}

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=maxCoinSize;
	init(maxCoinSize+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 (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]))
			{
				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 (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 176 ms 375996 KB Output is correct
2 Correct 162 ms 376028 KB Output is correct
3 Correct 171 ms 375976 KB Output is correct
4 Correct 159 ms 375988 KB Output is correct
5 Correct 184 ms 376004 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 375996 KB Output is correct
2 Correct 162 ms 376028 KB Output is correct
3 Correct 171 ms 375976 KB Output is correct
4 Correct 159 ms 375988 KB Output is correct
5 Correct 184 ms 376004 KB Output is correct
6 Correct 158 ms 376008 KB Output is correct
7 Correct 188 ms 376012 KB Output is correct
8 Correct 221 ms 376616 KB Output is correct
9 Correct 206 ms 376720 KB Output is correct
10 Correct 214 ms 376688 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 375996 KB Output is correct
2 Correct 162 ms 376028 KB Output is correct
3 Correct 171 ms 375976 KB Output is correct
4 Correct 159 ms 375988 KB Output is correct
5 Correct 184 ms 376004 KB Output is correct
6 Correct 1099 ms 383024 KB Output is correct
7 Correct 1093 ms 382940 KB Output is correct
8 Correct 1160 ms 382996 KB Output is correct
9 Correct 1638 ms 383176 KB Output is correct
10 Correct 1825 ms 386176 KB Output is correct
11 Correct 856 ms 388676 KB Output is correct
12 Correct 834 ms 388676 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 375996 KB Output is correct
2 Correct 162 ms 376028 KB Output is correct
3 Correct 171 ms 375976 KB Output is correct
4 Correct 159 ms 375988 KB Output is correct
5 Correct 184 ms 376004 KB Output is correct
6 Correct 158 ms 376008 KB Output is correct
7 Correct 188 ms 376012 KB Output is correct
8 Correct 221 ms 376616 KB Output is correct
9 Correct 206 ms 376720 KB Output is correct
10 Correct 214 ms 376688 KB Output is correct
11 Correct 1099 ms 383024 KB Output is correct
12 Correct 1093 ms 382940 KB Output is correct
13 Correct 1160 ms 382996 KB Output is correct
14 Correct 1638 ms 383176 KB Output is correct
15 Correct 1825 ms 386176 KB Output is correct
16 Correct 856 ms 388676 KB Output is correct
17 Correct 834 ms 388676 KB Output is correct
18 Execution timed out 2093 ms 524288 KB Time limit exceeded
19 Halted 0 ms 0 KB -