oj.uz

Submission #501259

# Submission time Handle Problem Language Result Execution time Memory
501259 2022-01-02T17:06:32 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1848 ms 503668 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+7);
	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 215 ms 501148 KB Output is correct
2 Correct 219 ms 501164 KB Output is correct
3 Correct 283 ms 501248 KB Output is correct
4 Correct 253 ms 501224 KB Output is correct
5 Correct 204 ms 501220 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 501148 KB Output is correct
2 Correct 219 ms 501164 KB Output is correct
3 Correct 283 ms 501248 KB Output is correct
4 Correct 253 ms 501224 KB Output is correct
5 Correct 204 ms 501220 KB Output is correct
6 Correct 225 ms 501284 KB Output is correct
7 Correct 219 ms 501380 KB Output is correct
8 Correct 251 ms 501452 KB Output is correct
9 Correct 273 ms 501520 KB Output is correct
10 Correct 278 ms 501428 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 501148 KB Output is correct
2 Correct 219 ms 501164 KB Output is correct
3 Correct 283 ms 501248 KB Output is correct
4 Correct 253 ms 501224 KB Output is correct
5 Correct 204 ms 501220 KB Output is correct
6 Correct 764 ms 503124 KB Output is correct
7 Correct 693 ms 502960 KB Output is correct
8 Correct 744 ms 503004 KB Output is correct
9 Correct 1010 ms 502952 KB Output is correct
10 Correct 985 ms 502952 KB Output is correct
11 Correct 666 ms 502152 KB Output is correct
12 Correct 648 ms 502136 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 501148 KB Output is correct
2 Correct 219 ms 501164 KB Output is correct
3 Correct 283 ms 501248 KB Output is correct
4 Correct 253 ms 501224 KB Output is correct
5 Correct 204 ms 501220 KB Output is correct
6 Correct 225 ms 501284 KB Output is correct
7 Correct 219 ms 501380 KB Output is correct
8 Correct 251 ms 501452 KB Output is correct
9 Correct 273 ms 501520 KB Output is correct
10 Correct 278 ms 501428 KB Output is correct
11 Correct 764 ms 503124 KB Output is correct
12 Correct 693 ms 502960 KB Output is correct
13 Correct 744 ms 503004 KB Output is correct
14 Correct 1010 ms 502952 KB Output is correct
15 Correct 985 ms 502952 KB Output is correct
16 Correct 666 ms 502152 KB Output is correct
17 Correct 648 ms 502136 KB Output is correct
18 Correct 1221 ms 503280 KB Output is correct
19 Correct 1285 ms 503668 KB Output is correct
20 Correct 1848 ms 503448 KB Output is correct
21 Correct 1162 ms 503004 KB Output is correct
22 Correct 1014 ms 502228 KB Output is correct
23 Correct 1036 ms 502252 KB Output is correct
24 Correct 1198 ms 502988 KB Output is correct