oj.uz

Submission #708890

# Submission time Handle Problem Language Result Execution time Memory
708890 2023-03-12T15:21:26 Z mars4 Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1790 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;
	int cnt;

	Node(): left(-1), right(-1), val(0), lazy(0), cnt(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,ll op)
{
	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)
	{
		if(op==1)
		{
			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;
			_push(ind,st,ed,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].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,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 221 ms 501156 KB Output is correct
2 Correct 199 ms 501164 KB Output is correct
3 Correct 204 ms 501184 KB Output is correct
4 Correct 254 ms 501196 KB Output is correct
5 Correct 218 ms 501168 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 501156 KB Output is correct
2 Correct 199 ms 501164 KB Output is correct
3 Correct 204 ms 501184 KB Output is correct
4 Correct 254 ms 501196 KB Output is correct
5 Correct 218 ms 501168 KB Output is correct
6 Correct 218 ms 501184 KB Output is correct
7 Correct 235 ms 501184 KB Output is correct
8 Correct 227 ms 501320 KB Output is correct
9 Correct 262 ms 501236 KB Output is correct
10 Correct 231 ms 501340 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 501156 KB Output is correct
2 Correct 199 ms 501164 KB Output is correct
3 Correct 204 ms 501184 KB Output is correct
4 Correct 254 ms 501196 KB Output is correct
5 Correct 218 ms 501168 KB Output is correct
6 Correct 650 ms 502352 KB Output is correct
7 Correct 735 ms 502280 KB Output is correct
8 Correct 653 ms 502132 KB Output is correct
9 Correct 933 ms 502180 KB Output is correct
10 Correct 928 ms 502240 KB Output is correct
11 Correct 541 ms 501448 KB Output is correct
12 Correct 514 ms 501508 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 501156 KB Output is correct
2 Correct 199 ms 501164 KB Output is correct
3 Correct 204 ms 501184 KB Output is correct
4 Correct 254 ms 501196 KB Output is correct
5 Correct 218 ms 501168 KB Output is correct
6 Correct 218 ms 501184 KB Output is correct
7 Correct 235 ms 501184 KB Output is correct
8 Correct 227 ms 501320 KB Output is correct
9 Correct 262 ms 501236 KB Output is correct
10 Correct 231 ms 501340 KB Output is correct
11 Correct 650 ms 502352 KB Output is correct
12 Correct 735 ms 502280 KB Output is correct
13 Correct 653 ms 502132 KB Output is correct
14 Correct 933 ms 502180 KB Output is correct
15 Correct 928 ms 502240 KB Output is correct
16 Correct 541 ms 501448 KB Output is correct
17 Correct 514 ms 501508 KB Output is correct
18 Correct 1221 ms 502216 KB Output is correct
19 Correct 1198 ms 502312 KB Output is correct
20 Runtime error 1790 ms 524288 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -