oj.uz

Submission #708888

# Submission time Handle Problem Language Result Execution time Memory
708888 2023-03-12T14:50:57 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1603 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 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;
	}
}

void _push(ll ind,ll st,ll ed,ll val)
{
	if(st!=ed)
	{
		extend(ind);
		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(st>ed or st>r or ed<l)
	{
		return;
	}
	if(T[ind].lazy)
	{
		T[ind].val+=T[ind].lazy;
		_push(ind,st,ed,T[ind].lazy);
		T[ind].lazy=0;
	}
	if(st>=l and ed<=r)
	{
		T[ind].val+=val;
		_push(ind,st,ed,val);
		return;
	}
	ll mid=(st+ed)>>1;
	extend(ind);
	_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].left].lazy,T[T[ind].right].val+T[T[ind].right].lazy);
}

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

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

gp_hash_table<int,int> mp;
ll ed;

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

bool is_happy(int event, int coinsCount, long long coins[])
{
	if(event==1)
	{
		forn(i,0,coinsCount)
		{
			if(mp[coins[i]]==0)
			{
				update(coins[i],coins[i],-coins[i]);
			}
			mp[coins[i]]++;
			update(coins[i]+1,ed,coins[i]);
		}
	}
	else
	{
		forn(i,0,coinsCount)
		{
			update(coins[i]+1,ed,-coins[i]);
			mp[coins[i]]--;
			if(mp[coins[i]]==0)
			{
				mp.erase(coins[i]);
				update(coins[i],coins[i],coins[i]);
			}
		}
	}
	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 175 ms 375904 KB Output is correct
2 Correct 151 ms 376024 KB Output is correct
3 Correct 153 ms 376072 KB Output is correct
4 Correct 161 ms 375916 KB Output is correct
5 Correct 185 ms 375948 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 375904 KB Output is correct
2 Correct 151 ms 376024 KB Output is correct
3 Correct 153 ms 376072 KB Output is correct
4 Correct 161 ms 375916 KB Output is correct
5 Correct 185 ms 375948 KB Output is correct
6 Correct 163 ms 376072 KB Output is correct
7 Correct 159 ms 376016 KB Output is correct
8 Correct 178 ms 376808 KB Output is correct
9 Correct 221 ms 376720 KB Output is correct
10 Correct 187 ms 376720 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 375904 KB Output is correct
2 Correct 151 ms 376024 KB Output is correct
3 Correct 153 ms 376072 KB Output is correct
4 Correct 161 ms 375916 KB Output is correct
5 Correct 185 ms 375948 KB Output is correct
6 Correct 721 ms 381552 KB Output is correct
7 Correct 737 ms 381488 KB Output is correct
8 Correct 662 ms 381564 KB Output is correct
9 Correct 1056 ms 381432 KB Output is correct
10 Correct 951 ms 386200 KB Output is correct
11 Correct 515 ms 385452 KB Output is correct
12 Correct 549 ms 385428 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 375904 KB Output is correct
2 Correct 151 ms 376024 KB Output is correct
3 Correct 153 ms 376072 KB Output is correct
4 Correct 161 ms 375916 KB Output is correct
5 Correct 185 ms 375948 KB Output is correct
6 Correct 163 ms 376072 KB Output is correct
7 Correct 159 ms 376016 KB Output is correct
8 Correct 178 ms 376808 KB Output is correct
9 Correct 221 ms 376720 KB Output is correct
10 Correct 187 ms 376720 KB Output is correct
11 Correct 721 ms 381552 KB Output is correct
12 Correct 737 ms 381488 KB Output is correct
13 Correct 662 ms 381564 KB Output is correct
14 Correct 1056 ms 381432 KB Output is correct
15 Correct 951 ms 386200 KB Output is correct
16 Correct 515 ms 385452 KB Output is correct
17 Correct 549 ms 385428 KB Output is correct
18 Correct 1166 ms 381492 KB Output is correct
19 Correct 1178 ms 381560 KB Output is correct
20 Runtime error 1603 ms 524288 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -