oj.uz

Submission #501168

# Submission time Handle Problem Language Result Execution time Memory
501168 2022-01-02T13:53:10 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
30 / 100
 2000 ms 372272 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);
}

gp_hash_table<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.find(coins[i])==cnt.end())
		{
			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.find(coins[i])==cnt.end())
			{
				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.find(coins[i])==cnt.end())
			{
				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 135 ms 352496 KB Output is correct
2 Correct 132 ms 352428 KB Output is correct
3 Correct 133 ms 352436 KB Output is correct
4 Correct 136 ms 352596 KB Output is correct
5 Correct 142 ms 352460 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 352496 KB Output is correct
2 Correct 132 ms 352428 KB Output is correct
3 Correct 133 ms 352436 KB Output is correct
4 Correct 136 ms 352596 KB Output is correct
5 Correct 142 ms 352460 KB Output is correct
6 Correct 158 ms 352664 KB Output is correct
7 Correct 138 ms 352708 KB Output is correct
8 Correct 179 ms 353936 KB Output is correct
9 Correct 165 ms 353952 KB Output is correct
10 Correct 158 ms 353840 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 352496 KB Output is correct
2 Correct 132 ms 352428 KB Output is correct
3 Correct 133 ms 352436 KB Output is correct
4 Correct 136 ms 352596 KB Output is correct
5 Correct 142 ms 352460 KB Output is correct
6 Correct 656 ms 362828 KB Output is correct
7 Correct 800 ms 362676 KB Output is correct
8 Correct 638 ms 362664 KB Output is correct
9 Correct 913 ms 362660 KB Output is correct
10 Correct 928 ms 372272 KB Output is correct
11 Execution timed out 2099 ms 371108 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 352496 KB Output is correct
2 Correct 132 ms 352428 KB Output is correct
3 Correct 133 ms 352436 KB Output is correct
4 Correct 136 ms 352596 KB Output is correct
5 Correct 142 ms 352460 KB Output is correct
6 Correct 158 ms 352664 KB Output is correct
7 Correct 138 ms 352708 KB Output is correct
8 Correct 179 ms 353936 KB Output is correct
9 Correct 165 ms 353952 KB Output is correct
10 Correct 158 ms 353840 KB Output is correct
11 Correct 656 ms 362828 KB Output is correct
12 Correct 800 ms 362676 KB Output is correct
13 Correct 638 ms 362664 KB Output is correct
14 Correct 913 ms 362660 KB Output is correct
15 Correct 928 ms 372272 KB Output is correct
16 Execution timed out 2099 ms 371108 KB Time limit exceeded
17 Halted 0 ms 0 KB -