oj.uz

Submission #708900

# Submission time Handle Problem Language Result Execution time Memory
708900 2023-03-12T15:37:30 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1387 ms 384732 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 i128            __int128_t
#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 T> ostream& operator<<(ostream& out,ordered_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;

struct Node
{
	int left;
	int right;
	ll val;
	ll lazy;

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

Node T[16'000'000];

void extend(ll cind)
{
	if(T[cind].left==-1)
	{
		T[cind].left=++ind;
		T[cind].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==1)
		{
			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;
	extend(ind);
	_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;
}

void init(ll n)
{
	ind=0;
	N=n;
}

void update(ll l,ll r,ll val,ll op)
{
	_update(0,0,N-1,l,r,val,op);
}

ll ed;

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

bool is_happy(int event, int coinsCount, long long coins[])
{
	forn(i,0,coinsCount)
	{
		update(coins[i],coins[i],event*coins[i],1);
		update(coins[i]+1,ed,event*coins[i],2);
	}
	return T[0].val+T[0].lazy>=-1;
}

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 158 ms 376012 KB Output is correct
2 Correct 147 ms 376020 KB Output is correct
3 Correct 152 ms 375908 KB Output is correct
4 Correct 175 ms 375944 KB Output is correct
5 Correct 156 ms 376012 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 376012 KB Output is correct
2 Correct 147 ms 376020 KB Output is correct
3 Correct 152 ms 375908 KB Output is correct
4 Correct 175 ms 375944 KB Output is correct
5 Correct 156 ms 376012 KB Output is correct
6 Correct 159 ms 376012 KB Output is correct
7 Correct 156 ms 376080 KB Output is correct
8 Correct 221 ms 375992 KB Output is correct
9 Correct 192 ms 376012 KB Output is correct
10 Correct 179 ms 376024 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 376012 KB Output is correct
2 Correct 147 ms 376020 KB Output is correct
3 Correct 152 ms 375908 KB Output is correct
4 Correct 175 ms 375944 KB Output is correct
5 Correct 156 ms 376012 KB Output is correct
6 Correct 557 ms 376916 KB Output is correct
7 Correct 557 ms 377044 KB Output is correct
8 Correct 535 ms 377004 KB Output is correct
9 Correct 731 ms 377000 KB Output is correct
10 Correct 804 ms 376916 KB Output is correct
11 Correct 433 ms 376116 KB Output is correct
12 Correct 467 ms 376132 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 376012 KB Output is correct
2 Correct 147 ms 376020 KB Output is correct
3 Correct 152 ms 375908 KB Output is correct
4 Correct 175 ms 375944 KB Output is correct
5 Correct 156 ms 376012 KB Output is correct
6 Correct 159 ms 376012 KB Output is correct
7 Correct 156 ms 376080 KB Output is correct
8 Correct 221 ms 375992 KB Output is correct
9 Correct 192 ms 376012 KB Output is correct
10 Correct 179 ms 376024 KB Output is correct
11 Correct 557 ms 376916 KB Output is correct
12 Correct 557 ms 377044 KB Output is correct
13 Correct 535 ms 377004 KB Output is correct
14 Correct 731 ms 377000 KB Output is correct
15 Correct 804 ms 376916 KB Output is correct
16 Correct 433 ms 376116 KB Output is correct
17 Correct 467 ms 376132 KB Output is correct
18 Correct 945 ms 377032 KB Output is correct
19 Correct 933 ms 376928 KB Output is correct
20 Correct 1387 ms 384732 KB Output is correct
21 Correct 859 ms 381884 KB Output is correct
22 Correct 694 ms 382020 KB Output is correct
23 Correct 681 ms 382412 KB Output is correct
24 Correct 899 ms 382284 KB Output is correct