oj.uz

Submission #501144

# Submission time Handle Problem Language Result Execution time Memory
501144 2022-01-02T13:18:11 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1835 ms 524288 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];

void _push(ll ind,ll st,ll ed,ll val)
{
	if(st!=ed)
	{
		T[ind].extend();
		T[T[ind].left].lazy+=val;
		T[T[ind].right].lazy+=val;
	}
}

ll combine(ll a,ll b)
{
	return min(a,b);
}

void _update(ll ind,ll st,ll ed,ll l,ll r,ll val)
{
	if(T[ind].lazy)
	{
		T[ind].val+=T[ind].lazy;
		_push(ind,st,ed,T[ind].lazy);
		T[ind].lazy=0;
	}
	if(st>ed or st>r or ed<l)
	{
		return;
	}
	if(st>=l and ed<=r)
	{
		T[ind].val+=val;
		_push(ind,st,ed,val);
		return;
	}
	ll mid=(st+ed)>>1;
	T[ind].extend();
	_update(T[ind].left,st,mid,l,r,val);
	_update(T[ind].right,mid+1,ed,l,r,val);
	T[ind].val=combine(T[T[ind].left].val,T[T[ind].right].val);
}

ll _query(ll ind,ll st,ll ed,ll l,ll r)
{
	if(T[ind].lazy)
	{
		T[ind].val+=T[ind].lazy;
		_push(ind,st,ed,T[ind].lazy);
		T[ind].lazy=0;
	}
	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));
}

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

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

ll query(ll l,ll r)
{
	return _query(0,0,N-1,l,r);
}

map<ll,ll> cnt;
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)
	{
		if(!cnt.count(coins[i]))
		{
			update(coins[i],coins[i],-coins[i]);
		}
		update(coins[i]+1,MX,coins[i]);
		cnt[coins[i]]++;
	}
	if(cnt.empty())
	{
		return true;
	}
	return (T[0].val>=0);
}

bool is_happy(int event,int coinsCount,long long coins[])
{
	if(event==1)
	{
		forn(i,0,coinsCount)
		{
			if(!cnt.count(coins[i]))
			{
				update(coins[i],coins[i],-coins[i]);
			}
			update(coins[i]+1,MX,coins[i]);
			cnt[coins[i]]++;
		}
	}
	else
	{
		forn(i,0,coinsCount)
		{
			cnt[coins[i]]--;
			if(cnt[coins[i]]==0)
			{
				cnt.erase(coins[i]);
			}
			if(!cnt.count(coins[i]))
			{
				update(coins[i],coins[i],coins[i]);
			}
			update(coins[i]+1,MX,-coins[i]);
		}
	}
	if(cnt.empty())
	{
		return true;
	}
	return (T[0].val>=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 177 ms 352476 KB Output is correct
2 Correct 158 ms 352508 KB Output is correct
3 Correct 156 ms 352444 KB Output is correct
4 Correct 154 ms 352420 KB Output is correct
5 Correct 155 ms 352488 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 352476 KB Output is correct
2 Correct 158 ms 352508 KB Output is correct
3 Correct 156 ms 352444 KB Output is correct
4 Correct 154 ms 352420 KB Output is correct
5 Correct 155 ms 352488 KB Output is correct
6 Correct 179 ms 352492 KB Output is correct
7 Correct 164 ms 352504 KB Output is correct
8 Correct 199 ms 353348 KB Output is correct
9 Correct 206 ms 353456 KB Output is correct
10 Correct 195 ms 353340 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 352476 KB Output is correct
2 Correct 158 ms 352508 KB Output is correct
3 Correct 156 ms 352444 KB Output is correct
4 Correct 154 ms 352420 KB Output is correct
5 Correct 155 ms 352488 KB Output is correct
6 Correct 1061 ms 360052 KB Output is correct
7 Correct 1020 ms 359896 KB Output is correct
8 Correct 1054 ms 360024 KB Output is correct
9 Correct 1590 ms 360276 KB Output is correct
10 Correct 1695 ms 363408 KB Output is correct
11 Correct 839 ms 365948 KB Output is correct
12 Correct 784 ms 365856 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 352476 KB Output is correct
2 Correct 158 ms 352508 KB Output is correct
3 Correct 156 ms 352444 KB Output is correct
4 Correct 154 ms 352420 KB Output is correct
5 Correct 155 ms 352488 KB Output is correct
6 Correct 179 ms 352492 KB Output is correct
7 Correct 164 ms 352504 KB Output is correct
8 Correct 199 ms 353348 KB Output is correct
9 Correct 206 ms 353456 KB Output is correct
10 Correct 195 ms 353340 KB Output is correct
11 Correct 1061 ms 360052 KB Output is correct
12 Correct 1020 ms 359896 KB Output is correct
13 Correct 1054 ms 360024 KB Output is correct
14 Correct 1590 ms 360276 KB Output is correct
15 Correct 1695 ms 363408 KB Output is correct
16 Correct 839 ms 365948 KB Output is correct
17 Correct 784 ms 365856 KB Output is correct
18 Runtime error 1835 ms 524288 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -