oj.uz

Submission #501143

# Submission time Handle Problem Language Result Execution time Memory
501143 2022-01-02T13:13:58 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1733 ms 493732 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[10000000];

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 (T[0].val>=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>=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 105 ms 235100 KB Output is correct
2 Correct 98 ms 235100 KB Output is correct
3 Correct 108 ms 235068 KB Output is correct
4 Correct 131 ms 235080 KB Output is correct
5 Correct 101 ms 235024 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 235100 KB Output is correct
2 Correct 98 ms 235100 KB Output is correct
3 Correct 108 ms 235068 KB Output is correct
4 Correct 131 ms 235080 KB Output is correct
5 Correct 101 ms 235024 KB Output is correct
6 Correct 100 ms 235168 KB Output is correct
7 Correct 103 ms 235096 KB Output is correct
8 Correct 173 ms 236020 KB Output is correct
9 Correct 150 ms 235972 KB Output is correct
10 Correct 141 ms 235924 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 235100 KB Output is correct
2 Correct 98 ms 235100 KB Output is correct
3 Correct 108 ms 235068 KB Output is correct
4 Correct 131 ms 235080 KB Output is correct
5 Correct 101 ms 235024 KB Output is correct
6 Correct 1006 ms 245032 KB Output is correct
7 Correct 1031 ms 244996 KB Output is correct
8 Correct 992 ms 244968 KB Output is correct
9 Correct 1596 ms 244928 KB Output is correct
10 Correct 1733 ms 247988 KB Output is correct
11 Correct 786 ms 250724 KB Output is correct
12 Correct 807 ms 250796 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 235100 KB Output is correct
2 Correct 98 ms 235100 KB Output is correct
3 Correct 108 ms 235068 KB Output is correct
4 Correct 131 ms 235080 KB Output is correct
5 Correct 101 ms 235024 KB Output is correct
6 Correct 100 ms 235168 KB Output is correct
7 Correct 103 ms 235096 KB Output is correct
8 Correct 173 ms 236020 KB Output is correct
9 Correct 150 ms 235972 KB Output is correct
10 Correct 141 ms 235924 KB Output is correct
11 Correct 1006 ms 245032 KB Output is correct
12 Correct 1031 ms 244996 KB Output is correct
13 Correct 992 ms 244968 KB Output is correct
14 Correct 1596 ms 244928 KB Output is correct
15 Correct 1733 ms 247988 KB Output is correct
16 Correct 786 ms 250724 KB Output is correct
17 Correct 807 ms 250796 KB Output is correct
18 Runtime error 1139 ms 493732 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -