oj.uz

Submission #708881

# Submission time Handle Problem Language Result Execution time Memory
708881 2023-03-12T14:37:59 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1826 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---------------------------------

ll N;
ll ind;

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

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

Node T[16'000'000];

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;
}

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);
}

ll first_element_atmost_x(ll l,ll r,ll val)
{
	return _first_element_atmost_x(0,0,N-1,l,r,val);
}
map<ll,ll> mp;
ll ed;

bool init(int coinsCount, long long maxCoinSize, long long coins[])
{
	ed=maxCoinSize+7;
	init(ed);
	forn(i,0,coinsCount)
	{
		if(!mp.count(coins[i]))
		{
			update(coins[i],coins[i],-coins[i]);
		}
		mp[coins[i]]++;
		update(coins[i]+1,ed,coins[i]);
	}
	return 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]))
			{
				update(coins[i],coins[i],-coins[i]);
			}
			mp[coins[i]]++;
			update(coins[i]+1,ed,coins[i]);
		}
	}
	else
	{
		forn(i,0,coinsCount)
		{
			update(coins[i]+1,ed,-coins[i]);
			mp[coins[i]]--;
			if(mp[coins[i]]==0)
			{
				mp.erase(coins[i]);
				update(coins[i],coins[i],coins[i]);
			}
		}
	}
	return 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 161 ms 375968 KB Output is correct
2 Correct 177 ms 376100 KB Output is correct
3 Correct 158 ms 376012 KB Output is correct
4 Correct 154 ms 375956 KB Output is correct
5 Correct 177 ms 375980 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 375968 KB Output is correct
2 Correct 177 ms 376100 KB Output is correct
3 Correct 158 ms 376012 KB Output is correct
4 Correct 154 ms 375956 KB Output is correct
5 Correct 177 ms 375980 KB Output is correct
6 Correct 161 ms 376008 KB Output is correct
7 Correct 157 ms 376140 KB Output is correct
8 Correct 189 ms 376696 KB Output is correct
9 Correct 202 ms 376656 KB Output is correct
10 Correct 189 ms 376716 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 375968 KB Output is correct
2 Correct 177 ms 376100 KB Output is correct
3 Correct 158 ms 376012 KB Output is correct
4 Correct 154 ms 375956 KB Output is correct
5 Correct 177 ms 375980 KB Output is correct
6 Correct 974 ms 383020 KB Output is correct
7 Correct 992 ms 382996 KB Output is correct
8 Correct 1030 ms 382912 KB Output is correct
9 Correct 1463 ms 383008 KB Output is correct
10 Correct 1574 ms 386208 KB Output is correct
11 Correct 685 ms 388768 KB Output is correct
12 Correct 671 ms 388692 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 375968 KB Output is correct
2 Correct 177 ms 376100 KB Output is correct
3 Correct 158 ms 376012 KB Output is correct
4 Correct 154 ms 375956 KB Output is correct
5 Correct 177 ms 375980 KB Output is correct
6 Correct 161 ms 376008 KB Output is correct
7 Correct 157 ms 376140 KB Output is correct
8 Correct 189 ms 376696 KB Output is correct
9 Correct 202 ms 376656 KB Output is correct
10 Correct 189 ms 376716 KB Output is correct
11 Correct 974 ms 383020 KB Output is correct
12 Correct 992 ms 382996 KB Output is correct
13 Correct 1030 ms 382912 KB Output is correct
14 Correct 1463 ms 383008 KB Output is correct
15 Correct 1574 ms 386208 KB Output is correct
16 Correct 685 ms 388768 KB Output is correct
17 Correct 671 ms 388692 KB Output is correct
18 Runtime error 1826 ms 524288 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -