oj.uz

Submission #501240

# Submission time Handle Problem Language Result Execution time Memory
501240 2022-01-02T16:46:15 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1622 ms 502828 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;
	int cnt;

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

	void extend()
	{
		if(left==-1)
		{
			left=++ind;
			right=++ind;
		}
	}
};

Node T[16'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,ll op)
{
	if(st>ed or st>r or ed<l)
	{
		return;
	}
	if(st>=l and ed<=r)
	{
		if(op==2)
		{
			if(val<0)
			{
				if(T[ind].cnt==0)
				{
					T[ind].val+=val;
				}
				T[ind].cnt++;
			}
			else
			{
				T[ind].cnt--;
				if(T[ind].cnt==0)
				{
					T[ind].val+=val;
				}
			}
		}
		else
		{
			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,op);
	_update(T[ind].right,mid+1,ed,l,r,val,op);
	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,ll op=1)
{
	_update(0,0,N-1,l,r,val,op);
}

ll query(ll l,ll r)
{
	return _query(0,0,N-1,l,r);
}

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)
	{
		update(coins[i],coins[i],-coins[i],2);
		update(coins[i]+1,MX,coins[i]);
	}
	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)
		{
			update(coins[i],coins[i],-coins[i],2);
			update(coins[i]+1,MX,coins[i]);
		}
	}
	else
	{
		forn(i,0,coinsCount)
		{
			update(coins[i],coins[i],coins[i],2);
			update(coins[i]+1,MX,-coins[i]);
		}
	}
	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 208 ms 501248 KB Output is correct
2 Correct 218 ms 501144 KB Output is correct
3 Correct 191 ms 501236 KB Output is correct
4 Correct 195 ms 501188 KB Output is correct
5 Correct 214 ms 501188 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 501248 KB Output is correct
2 Correct 218 ms 501144 KB Output is correct
3 Correct 191 ms 501236 KB Output is correct
4 Correct 195 ms 501188 KB Output is correct
5 Correct 214 ms 501188 KB Output is correct
6 Correct 193 ms 501160 KB Output is correct
7 Correct 224 ms 501276 KB Output is correct
8 Correct 245 ms 501440 KB Output is correct
9 Correct 218 ms 501444 KB Output is correct
10 Correct 249 ms 501452 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 501248 KB Output is correct
2 Correct 218 ms 501144 KB Output is correct
3 Correct 191 ms 501236 KB Output is correct
4 Correct 195 ms 501188 KB Output is correct
5 Correct 214 ms 501188 KB Output is correct
6 Correct 645 ms 502464 KB Output is correct
7 Correct 641 ms 502472 KB Output is correct
8 Correct 662 ms 502620 KB Output is correct
9 Correct 892 ms 502500 KB Output is correct
10 Correct 938 ms 502444 KB Output is correct
11 Correct 603 ms 501780 KB Output is correct
12 Correct 549 ms 501792 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 501248 KB Output is correct
2 Correct 218 ms 501144 KB Output is correct
3 Correct 191 ms 501236 KB Output is correct
4 Correct 195 ms 501188 KB Output is correct
5 Correct 214 ms 501188 KB Output is correct
6 Correct 193 ms 501160 KB Output is correct
7 Correct 224 ms 501276 KB Output is correct
8 Correct 245 ms 501440 KB Output is correct
9 Correct 218 ms 501444 KB Output is correct
10 Correct 249 ms 501452 KB Output is correct
11 Correct 645 ms 502464 KB Output is correct
12 Correct 641 ms 502472 KB Output is correct
13 Correct 662 ms 502620 KB Output is correct
14 Correct 892 ms 502500 KB Output is correct
15 Correct 938 ms 502444 KB Output is correct
16 Correct 603 ms 501780 KB Output is correct
17 Correct 549 ms 501792 KB Output is correct
18 Correct 1133 ms 502632 KB Output is correct
19 Correct 1042 ms 502828 KB Output is correct
20 Correct 1622 ms 502756 KB Output is correct
21 Correct 1042 ms 502756 KB Output is correct
22 Correct 914 ms 501908 KB Output is correct
23 Correct 871 ms 501960 KB Output is correct
24 Correct 1073 ms 502684 KB Output is correct