oj.uz

Submission #501060

# Submission time Handle Problem Language Result Execution time Memory
501060 2022-01-02T10:13:50 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1660 ms 395596 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(8'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 82 ms 188040 KB Output is correct
2 Correct 79 ms 188124 KB Output is correct
3 Correct 86 ms 188168 KB Output is correct
4 Correct 81 ms 188148 KB Output is correct
5 Correct 82 ms 188064 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 188040 KB Output is correct
2 Correct 79 ms 188124 KB Output is correct
3 Correct 86 ms 188168 KB Output is correct
4 Correct 81 ms 188148 KB Output is correct
5 Correct 82 ms 188064 KB Output is correct
6 Correct 84 ms 188140 KB Output is correct
7 Correct 89 ms 188300 KB Output is correct
8 Correct 133 ms 188852 KB Output is correct
9 Correct 132 ms 188740 KB Output is correct
10 Correct 130 ms 188828 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 188040 KB Output is correct
2 Correct 79 ms 188124 KB Output is correct
3 Correct 86 ms 188168 KB Output is correct
4 Correct 81 ms 188148 KB Output is correct
5 Correct 82 ms 188064 KB Output is correct
6 Correct 1000 ms 195176 KB Output is correct
7 Correct 1002 ms 195100 KB Output is correct
8 Correct 965 ms 195104 KB Output is correct
9 Correct 1566 ms 195412 KB Output is correct
10 Correct 1660 ms 198084 KB Output is correct
11 Correct 760 ms 201052 KB Output is correct
12 Correct 747 ms 200944 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 188040 KB Output is correct
2 Correct 79 ms 188124 KB Output is correct
3 Correct 86 ms 188168 KB Output is correct
4 Correct 81 ms 188148 KB Output is correct
5 Correct 82 ms 188064 KB Output is correct
6 Correct 84 ms 188140 KB Output is correct
7 Correct 89 ms 188300 KB Output is correct
8 Correct 133 ms 188852 KB Output is correct
9 Correct 132 ms 188740 KB Output is correct
10 Correct 130 ms 188828 KB Output is correct
11 Correct 1000 ms 195176 KB Output is correct
12 Correct 1002 ms 195100 KB Output is correct
13 Correct 965 ms 195104 KB Output is correct
14 Correct 1566 ms 195412 KB Output is correct
15 Correct 1660 ms 198084 KB Output is correct
16 Correct 760 ms 201052 KB Output is correct
17 Correct 747 ms 200944 KB Output is correct
18 Runtime error 581 ms 395596 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -