oj.uz

Submission #708873

# Submission time Handle Problem Language Result Execution time Memory
708873 2023-03-12T14:22:32 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1518 ms 522572 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>(8'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 96 ms 250700 KB Output is correct
2 Correct 107 ms 250888 KB Output is correct
3 Correct 105 ms 250748 KB Output is correct
4 Correct 111 ms 250696 KB Output is correct
5 Correct 103 ms 250696 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 250700 KB Output is correct
2 Correct 107 ms 250888 KB Output is correct
3 Correct 105 ms 250748 KB Output is correct
4 Correct 111 ms 250696 KB Output is correct
5 Correct 103 ms 250696 KB Output is correct
6 Correct 103 ms 250788 KB Output is correct
7 Correct 110 ms 250864 KB Output is correct
8 Correct 141 ms 251964 KB Output is correct
9 Correct 134 ms 251620 KB Output is correct
10 Correct 139 ms 251636 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 250700 KB Output is correct
2 Correct 107 ms 250888 KB Output is correct
3 Correct 105 ms 250748 KB Output is correct
4 Correct 111 ms 250696 KB Output is correct
5 Correct 103 ms 250696 KB Output is correct
6 Correct 880 ms 257996 KB Output is correct
7 Correct 824 ms 258088 KB Output is correct
8 Correct 875 ms 257956 KB Output is correct
9 Correct 1401 ms 257880 KB Output is correct
10 Correct 1518 ms 261016 KB Output is correct
11 Correct 612 ms 263680 KB Output is correct
12 Correct 606 ms 263736 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 250700 KB Output is correct
2 Correct 107 ms 250888 KB Output is correct
3 Correct 105 ms 250748 KB Output is correct
4 Correct 111 ms 250696 KB Output is correct
5 Correct 103 ms 250696 KB Output is correct
6 Correct 103 ms 250788 KB Output is correct
7 Correct 110 ms 250864 KB Output is correct
8 Correct 141 ms 251964 KB Output is correct
9 Correct 134 ms 251620 KB Output is correct
10 Correct 139 ms 251636 KB Output is correct
11 Correct 880 ms 257996 KB Output is correct
12 Correct 824 ms 258088 KB Output is correct
13 Correct 875 ms 257956 KB Output is correct
14 Correct 1401 ms 257880 KB Output is correct
15 Correct 1518 ms 261016 KB Output is correct
16 Correct 612 ms 263680 KB Output is correct
17 Correct 606 ms 263736 KB Output is correct
18 Runtime error 592 ms 522572 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -