oj.uz

Submission #501236

# Submission time Handle Problem Language Result Execution time Memory
501236 2022-01-02T16:41:27 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1550 ms 353720 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[15'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 142 ms 352548 KB Output is correct
2 Correct 151 ms 352516 KB Output is correct
3 Correct 135 ms 352436 KB Output is correct
4 Correct 136 ms 352584 KB Output is correct
5 Correct 160 ms 352572 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 352548 KB Output is correct
2 Correct 151 ms 352516 KB Output is correct
3 Correct 135 ms 352436 KB Output is correct
4 Correct 136 ms 352584 KB Output is correct
5 Correct 160 ms 352572 KB Output is correct
6 Correct 137 ms 352532 KB Output is correct
7 Correct 140 ms 352500 KB Output is correct
8 Correct 184 ms 352512 KB Output is correct
9 Correct 190 ms 352688 KB Output is correct
10 Correct 163 ms 352540 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 352548 KB Output is correct
2 Correct 151 ms 352516 KB Output is correct
3 Correct 135 ms 352436 KB Output is correct
4 Correct 136 ms 352584 KB Output is correct
5 Correct 160 ms 352572 KB Output is correct
6 Correct 601 ms 353692 KB Output is correct
7 Correct 574 ms 353424 KB Output is correct
8 Correct 593 ms 353476 KB Output is correct
9 Correct 871 ms 353476 KB Output is correct
10 Correct 878 ms 353448 KB Output is correct
11 Correct 542 ms 352752 KB Output is correct
12 Correct 512 ms 352700 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 352548 KB Output is correct
2 Correct 151 ms 352516 KB Output is correct
3 Correct 135 ms 352436 KB Output is correct
4 Correct 136 ms 352584 KB Output is correct
5 Correct 160 ms 352572 KB Output is correct
6 Correct 137 ms 352532 KB Output is correct
7 Correct 140 ms 352500 KB Output is correct
8 Correct 184 ms 352512 KB Output is correct
9 Correct 190 ms 352688 KB Output is correct
10 Correct 163 ms 352540 KB Output is correct
11 Correct 601 ms 353692 KB Output is correct
12 Correct 574 ms 353424 KB Output is correct
13 Correct 593 ms 353476 KB Output is correct
14 Correct 871 ms 353476 KB Output is correct
15 Correct 878 ms 353448 KB Output is correct
16 Correct 542 ms 352752 KB Output is correct
17 Correct 512 ms 352700 KB Output is correct
18 Correct 1053 ms 353500 KB Output is correct
19 Correct 1092 ms 353720 KB Output is correct
20 Incorrect 1550 ms 353520 KB Output isn't correct
21 Halted 0 ms 0 KB -