oj.uz

Submission #501239

# Submission time Handle Problem Language Result Execution time Memory
501239 2022-01-02T16:44:42 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1587 ms 476440 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;

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

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

Node T[20'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].lazy==0)
				{
					T[ind].val+=val;
				}
				T[ind].lazy++;
			}
			else
			{
				T[ind].lazy--;
				if(T[ind].lazy==0)
				{
					T[ind].val+=val;
				}
			}
		}
		else
		{
			T[ind].val+=val;
			if(st!=ed)
			{
				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 222 ms 469832 KB Output is correct
2 Correct 180 ms 469940 KB Output is correct
3 Correct 207 ms 469828 KB Output is correct
4 Correct 196 ms 469908 KB Output is correct
5 Correct 184 ms 469852 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 469832 KB Output is correct
2 Correct 180 ms 469940 KB Output is correct
3 Correct 207 ms 469828 KB Output is correct
4 Correct 196 ms 469908 KB Output is correct
5 Correct 184 ms 469852 KB Output is correct
6 Correct 222 ms 469924 KB Output is correct
7 Correct 193 ms 469860 KB Output is correct
8 Correct 217 ms 470016 KB Output is correct
9 Correct 231 ms 470024 KB Output is correct
10 Correct 210 ms 470000 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 469832 KB Output is correct
2 Correct 180 ms 469940 KB Output is correct
3 Correct 207 ms 469828 KB Output is correct
4 Correct 196 ms 469908 KB Output is correct
5 Correct 184 ms 469852 KB Output is correct
6 Correct 711 ms 470888 KB Output is correct
7 Correct 689 ms 470892 KB Output is correct
8 Correct 666 ms 470856 KB Output is correct
9 Correct 938 ms 470852 KB Output is correct
10 Correct 920 ms 470856 KB Output is correct
11 Correct 582 ms 470084 KB Output is correct
12 Correct 576 ms 470140 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 469832 KB Output is correct
2 Correct 180 ms 469940 KB Output is correct
3 Correct 207 ms 469828 KB Output is correct
4 Correct 196 ms 469908 KB Output is correct
5 Correct 184 ms 469852 KB Output is correct
6 Correct 222 ms 469924 KB Output is correct
7 Correct 193 ms 469860 KB Output is correct
8 Correct 217 ms 470016 KB Output is correct
9 Correct 231 ms 470024 KB Output is correct
10 Correct 210 ms 470000 KB Output is correct
11 Correct 711 ms 470888 KB Output is correct
12 Correct 689 ms 470892 KB Output is correct
13 Correct 666 ms 470856 KB Output is correct
14 Correct 938 ms 470852 KB Output is correct
15 Correct 920 ms 470856 KB Output is correct
16 Correct 582 ms 470084 KB Output is correct
17 Correct 576 ms 470140 KB Output is correct
18 Correct 1125 ms 470984 KB Output is correct
19 Correct 1137 ms 471064 KB Output is correct
20 Correct 1587 ms 470884 KB Output is correct
21 Correct 1072 ms 475844 KB Output is correct
22 Correct 989 ms 475876 KB Output is correct
23 Correct 979 ms 476440 KB Output is correct
24 Correct 1143 ms 476280 KB Output is correct