oj.uz

Submission #501154

# Submission time Handle Problem Language Result Execution time Memory
501154 2022-01-02T13:36:59 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 367512 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=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+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 166 ms 352532 KB Output is correct
2 Correct 169 ms 352484 KB Output is correct
3 Correct 168 ms 352528 KB Output is correct
4 Correct 157 ms 352416 KB Output is correct
5 Correct 162 ms 352528 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 352532 KB Output is correct
2 Correct 169 ms 352484 KB Output is correct
3 Correct 168 ms 352528 KB Output is correct
4 Correct 157 ms 352416 KB Output is correct
5 Correct 162 ms 352528 KB Output is correct
6 Correct 164 ms 352544 KB Output is correct
7 Correct 166 ms 352540 KB Output is correct
8 Correct 220 ms 353432 KB Output is correct
9 Correct 229 ms 353428 KB Output is correct
10 Correct 191 ms 353324 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 352532 KB Output is correct
2 Correct 169 ms 352484 KB Output is correct
3 Correct 168 ms 352528 KB Output is correct
4 Correct 157 ms 352416 KB Output is correct
5 Correct 162 ms 352528 KB Output is correct
6 Correct 994 ms 360620 KB Output is correct
7 Correct 907 ms 360820 KB Output is correct
8 Correct 912 ms 360856 KB Output is correct
9 Correct 1416 ms 361788 KB Output is correct
10 Correct 1559 ms 364868 KB Output is correct
11 Correct 753 ms 367220 KB Output is correct
12 Correct 790 ms 367388 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 352532 KB Output is correct
2 Correct 169 ms 352484 KB Output is correct
3 Correct 168 ms 352528 KB Output is correct
4 Correct 157 ms 352416 KB Output is correct
5 Correct 162 ms 352528 KB Output is correct
6 Correct 164 ms 352544 KB Output is correct
7 Correct 166 ms 352540 KB Output is correct
8 Correct 220 ms 353432 KB Output is correct
9 Correct 229 ms 353428 KB Output is correct
10 Correct 191 ms 353324 KB Output is correct
11 Correct 994 ms 360620 KB Output is correct
12 Correct 907 ms 360820 KB Output is correct
13 Correct 912 ms 360856 KB Output is correct
14 Correct 1416 ms 361788 KB Output is correct
15 Correct 1559 ms 364868 KB Output is correct
16 Correct 753 ms 367220 KB Output is correct
17 Correct 790 ms 367388 KB Output is correct
18 Correct 1535 ms 363128 KB Output is correct
19 Correct 1538 ms 365244 KB Output is correct
20 Execution timed out 2074 ms 367512 KB Time limit exceeded
21 Halted 0 ms 0 KB -