oj.uz

Submission #708872

# Submission time Handle Problem Language Result Execution time Memory
708872 2023-03-12T14:21:31 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 i128            __int128_t
#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 T> ostream& operator<<(ostream& out,ordered_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---------------------------------

class DynamicSegtree 
{
	ll N;
	ll ind;

	struct Node
	{
		ll left;
		ll right;
		ll val;
		ll lazy;

		Node(): left(-1), right(-1), val(0), lazy(0) {}
	};

	void extend(ll cind)
	{
		if(T[cind].left==-1)
		{
			T[cind].left=++ind;
			T[cind].right=++ind;
		}
	}

	void _push(ll ind,ll st,ll ed,ll val)
	{
		if(st!=ed)
		{
			extend(ind);
			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;
		extend(ind);
		_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;
		extend(ind);
		return combine(_query(T[ind].left,st,mid,l,r),_query(T[ind].right,mid+1,ed,l,r));
	}

	ll _first_element_atmost_x(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 or T[ind].val>val)
		{
			return -1;
		}
		if(st==ed)
		{
			return st;
		}
		ll mid=(st+ed)>>1;
		extend(ind);
		ll rind=_first_element_atmost_x(T[ind].left,st,mid,l,r,val);
		if(rind==-1)
		{
			rind=_first_element_atmost_x(T[ind].right,mid+1,ed,l,r,val);
		}
		return rind;
	}

	public:
	vector<Node> T;

	void init(ll n)
	{
		T=vector<Node>(16'000'000);
		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);
	}

	ll first_element_atmost_x(ll l,ll r,ll val)
	{
		return _first_element_atmost_x(0,0,N-1,l,r,val);
	}
};

DynamicSegtree s;
map<ll,ll> mp;
ll ed;

bool init(int coinsCount, long long maxCoinSize, long long coins[])
{
	ed=maxCoinSize+7;
	s.init(ed);
	forn(i,0,coinsCount)
	{
		if(!mp.count(coins[i]))
		{
			s.update(coins[i],coins[i],-coins[i]);
		}
		mp[coins[i]]++;
		s.update(coins[i]+1,ed,coins[i]);
	}
	return s.query(0,ed)>=-1;
}

bool is_happy(int event, int coinsCount, long long coins[])
{
	if(event==1)
	{
		forn(i,0,coinsCount)
		{
			if(!mp.count(coins[i]))
			{
				s.update(coins[i],coins[i],-coins[i]);
			}
			mp[coins[i]]++;
			s.update(coins[i]+1,ed,coins[i]);
		}
	}
	else
	{
		forn(i,0,coinsCount)
		{
			s.update(coins[i]+1,ed,-coins[i]);
			mp[coins[i]]--;
			if(mp[coins[i]]==0)
			{
				mp.erase(coins[i]);
				s.update(coins[i],coins[i],coins[i]);
			}
		}
	}
	return s.query(0,ed)>=-1;
}

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 188 ms 501176 KB Output is correct
2 Correct 192 ms 501164 KB Output is correct
3 Correct 194 ms 501320 KB Output is correct
4 Correct 192 ms 501196 KB Output is correct
5 Correct 189 ms 501192 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 501176 KB Output is correct
2 Correct 192 ms 501164 KB Output is correct
3 Correct 194 ms 501320 KB Output is correct
4 Correct 192 ms 501196 KB Output is correct
5 Correct 189 ms 501192 KB Output is correct
6 Correct 224 ms 501252 KB Output is correct
7 Correct 206 ms 501340 KB Output is correct
8 Correct 233 ms 502160 KB Output is correct
9 Correct 233 ms 502304 KB Output is correct
10 Correct 227 ms 502144 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 501176 KB Output is correct
2 Correct 192 ms 501164 KB Output is correct
3 Correct 194 ms 501320 KB Output is correct
4 Correct 192 ms 501196 KB Output is correct
5 Correct 189 ms 501192 KB Output is correct
6 Correct 991 ms 511372 KB Output is correct
7 Correct 905 ms 511216 KB Output is correct
8 Correct 930 ms 511252 KB Output is correct
9 Correct 1403 ms 512764 KB Output is correct
10 Correct 1548 ms 515728 KB Output is correct
11 Correct 684 ms 517776 KB Output is correct
12 Correct 697 ms 517956 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 501176 KB Output is correct
2 Correct 192 ms 501164 KB Output is correct
3 Correct 194 ms 501320 KB Output is correct
4 Correct 192 ms 501196 KB Output is correct
5 Correct 189 ms 501192 KB Output is correct
6 Correct 224 ms 501252 KB Output is correct
7 Correct 206 ms 501340 KB Output is correct
8 Correct 233 ms 502160 KB Output is correct
9 Correct 233 ms 502304 KB Output is correct
10 Correct 227 ms 502144 KB Output is correct
11 Correct 991 ms 511372 KB Output is correct
12 Correct 905 ms 511216 KB Output is correct
13 Correct 930 ms 511252 KB Output is correct
14 Correct 1403 ms 512764 KB Output is correct
15 Correct 1548 ms 515728 KB Output is correct
16 Correct 684 ms 517776 KB Output is correct
17 Correct 697 ms 517956 KB Output is correct
18 Execution timed out 2020 ms 524288 KB Time limit exceeded
19 Halted 0 ms 0 KB -