oj.uz

Submission #501252

# Submission time Handle Problem Language Result Execution time Memory
501252 2022-01-02T17:01:44 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1546 ms 502928 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---------------------------------

class DynamicSegtree
{
	ll N;
	static int ind;

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

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

	public:
	Node T[16'000'000];

	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;
DynamicSegtree ds;
int DynamicSegtree::ind;

bool init(int coinsCount,long long maxCoinSize,long long coins[])
{
	MX=maxCoinSize;
	ds.init(maxCoinSize+100);
	ds.update(0,MX,1);
	forn(i,0,coinsCount)
	{
		ds.update(coins[i],coins[i],-coins[i],2);
		ds.update(coins[i]+1,MX,coins[i]);
	}
	return (ds.T[0].val+ds.T[0].lazy>=0);
}

bool is_happy(int event,int coinsCount,long long coins[])
{
	if(event==1)
	{
		forn(i,0,coinsCount)
		{
			ds.update(coins[i],coins[i],-coins[i],2);
			ds.update(coins[i]+1,MX,coins[i]);
		}
	}
	else
	{
		forn(i,0,coinsCount)
		{
			ds.update(coins[i],coins[i],coins[i],2);
			ds.update(coins[i]+1,MX,-coins[i]);
		}
	}
	return (ds.T[0].val+ds.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 190 ms 501232 KB Output is correct
2 Correct 191 ms 501236 KB Output is correct
3 Correct 194 ms 501180 KB Output is correct
4 Correct 191 ms 501140 KB Output is correct
5 Correct 191 ms 501188 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 501232 KB Output is correct
2 Correct 191 ms 501236 KB Output is correct
3 Correct 194 ms 501180 KB Output is correct
4 Correct 191 ms 501140 KB Output is correct
5 Correct 191 ms 501188 KB Output is correct
6 Correct 204 ms 501384 KB Output is correct
7 Correct 196 ms 501188 KB Output is correct
8 Correct 217 ms 501392 KB Output is correct
9 Correct 232 ms 501512 KB Output is correct
10 Correct 215 ms 501364 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 501232 KB Output is correct
2 Correct 191 ms 501236 KB Output is correct
3 Correct 194 ms 501180 KB Output is correct
4 Correct 191 ms 501140 KB Output is correct
5 Correct 191 ms 501188 KB Output is correct
6 Correct 616 ms 502676 KB Output is correct
7 Correct 614 ms 502496 KB Output is correct
8 Correct 612 ms 502496 KB Output is correct
9 Correct 858 ms 502596 KB Output is correct
10 Correct 857 ms 502496 KB Output is correct
11 Correct 586 ms 501660 KB Output is correct
12 Correct 591 ms 501852 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 501232 KB Output is correct
2 Correct 191 ms 501236 KB Output is correct
3 Correct 194 ms 501180 KB Output is correct
4 Correct 191 ms 501140 KB Output is correct
5 Correct 191 ms 501188 KB Output is correct
6 Correct 204 ms 501384 KB Output is correct
7 Correct 196 ms 501188 KB Output is correct
8 Correct 217 ms 501392 KB Output is correct
9 Correct 232 ms 501512 KB Output is correct
10 Correct 215 ms 501364 KB Output is correct
11 Correct 616 ms 502676 KB Output is correct
12 Correct 614 ms 502496 KB Output is correct
13 Correct 612 ms 502496 KB Output is correct
14 Correct 858 ms 502596 KB Output is correct
15 Correct 857 ms 502496 KB Output is correct
16 Correct 586 ms 501660 KB Output is correct
17 Correct 591 ms 501852 KB Output is correct
18 Correct 1107 ms 502588 KB Output is correct
19 Correct 1066 ms 502660 KB Output is correct
20 Correct 1546 ms 502928 KB Output is correct
21 Correct 1041 ms 502472 KB Output is correct
22 Correct 895 ms 501644 KB Output is correct
23 Correct 923 ms 501956 KB Output is correct
24 Correct 1040 ms 502696 KB Output is correct