oj.uz

Submission #501257

# Submission time Handle Problem Language Result Execution time Memory
501257 2022-01-02T17:05:32 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1736 ms 502412 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+2);
	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 191 ms 501180 KB Output is correct
2 Correct 219 ms 501232 KB Output is correct
3 Correct 224 ms 501208 KB Output is correct
4 Correct 201 ms 501196 KB Output is correct
5 Correct 202 ms 501320 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 501180 KB Output is correct
2 Correct 219 ms 501232 KB Output is correct
3 Correct 224 ms 501208 KB Output is correct
4 Correct 201 ms 501196 KB Output is correct
5 Correct 202 ms 501320 KB Output is correct
6 Correct 200 ms 501236 KB Output is correct
7 Correct 225 ms 501224 KB Output is correct
8 Correct 218 ms 501268 KB Output is correct
9 Correct 217 ms 501288 KB Output is correct
10 Correct 238 ms 501212 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 501180 KB Output is correct
2 Correct 219 ms 501232 KB Output is correct
3 Correct 224 ms 501208 KB Output is correct
4 Correct 201 ms 501196 KB Output is correct
5 Correct 202 ms 501320 KB Output is correct
6 Correct 665 ms 502176 KB Output is correct
7 Correct 630 ms 502320 KB Output is correct
8 Correct 639 ms 502288 KB Output is correct
9 Correct 889 ms 502180 KB Output is correct
10 Correct 922 ms 502184 KB Output is correct
11 Correct 584 ms 501424 KB Output is correct
12 Correct 545 ms 501416 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 501180 KB Output is correct
2 Correct 219 ms 501232 KB Output is correct
3 Correct 224 ms 501208 KB Output is correct
4 Correct 201 ms 501196 KB Output is correct
5 Correct 202 ms 501320 KB Output is correct
6 Correct 200 ms 501236 KB Output is correct
7 Correct 225 ms 501224 KB Output is correct
8 Correct 218 ms 501268 KB Output is correct
9 Correct 217 ms 501288 KB Output is correct
10 Correct 238 ms 501212 KB Output is correct
11 Correct 665 ms 502176 KB Output is correct
12 Correct 630 ms 502320 KB Output is correct
13 Correct 639 ms 502288 KB Output is correct
14 Correct 889 ms 502180 KB Output is correct
15 Correct 922 ms 502184 KB Output is correct
16 Correct 584 ms 501424 KB Output is correct
17 Correct 545 ms 501416 KB Output is correct
18 Correct 1122 ms 502412 KB Output is correct
19 Correct 1070 ms 502232 KB Output is correct
20 Correct 1736 ms 502112 KB Output is correct
21 Correct 1066 ms 502296 KB Output is correct
22 Correct 887 ms 501436 KB Output is correct
23 Correct 1014 ms 501560 KB Output is correct
24 Correct 1088 ms 502340 KB Output is correct