oj.uz

Submission #641418

# Submission time Handle Problem Language Result Execution time Memory
641418 2022-09-16T16:53:58 Z itnes Happiness (Balkan15_HAPPINESS) C++14
30 / 100
 1800 ms 103072 KB 
#include "happiness.h"
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
const ll INFLL=1e18+7;
const int INF=1e9+7;
#define pb push_back
const int MAXN=2e5+7;
const ll nTree=(1LL<<40);
struct spr_tree{
	struct node{
		node *left_node=nullptr,*right_node=nullptr;
		ll val=0,lazy=0;
	};
	node *root=new node();
	void update(node *v,ll start,ll end,ll l,ll r,ll val){
		if(v->lazy!=0){
			v->val+=v->lazy;
			if(start!=end){
				if(v->left_node==nullptr) v->left_node=new node();
				v->left_node->lazy+=v->lazy;
				if(v->right_node==nullptr) v->right_node=new node();
				v->right_node->lazy+=v->lazy;
			}
			v->lazy=0;
		}
		if(start>r||end<l||start>end) return;
		if(start>=l&&end<=r){
			v->val+=val;
			if(start!=end){
				if(v->left_node==nullptr) v->left_node=new node();
				v->left_node->lazy+=val;
				if(v->right_node==nullptr) v->right_node=new node();
				v->right_node->lazy+=val;
			}
			return;
		}
		ll mid=(start+end)>>1;
		if(l<=mid||v->left_node!=nullptr){
			if(v->left_node==nullptr) v->left_node=new node();
			update(v->left_node,start,mid,l,r,val);
		}
		if(r>mid||v->right_node!=nullptr){
			if(v->right_node==nullptr) v->right_node=new node();
			update(v->right_node,mid+1,end,l,r,val);
		}
		v->val=max((v->left_node==nullptr?-INFLL:v->left_node->val),(v->right_node==nullptr?-INFLL:v->right_node->val));
	}
	ll query(node *v,ll start,ll end,ll l,ll r){
		if(start>r||end<l||start>end) return -INFLL;
		if(v->lazy!=0){
			v->val+=v->lazy;
			if(start!=end){
				if(v->left_node==nullptr) v->left_node=new node();
				v->left_node->lazy+=v->lazy;
				if(v->right_node==nullptr) v->right_node=new node();
				v->right_node->lazy+=v->lazy;
			}
			v->lazy=0;
		}
		if(start>=l&&end<=r) return v->val;
		ll mid=(start+end)>>1;
		ll val1=-INFLL,val2=-INFLL;
		if(l<=mid) val1=query(v->left_node,start,mid,l,r);
		if(r>mid) val2=query(v->right_node,mid+1,end,l,r);
		return max(val1,val2);
	}
	void update(ll l,ll r,ll val){update(root,0,nTree-1,l,r,val);}
	ll query(ll l,ll r){return query(root,0,nTree-1,l,r);}
};
ll N;
map<ll,int> cnt;
spr_tree t;
bool init(int coinsCount,ll maxCoinSize,ll coins[]){
	N=maxCoinSize;
	for(int i=0;i<coinsCount;++i){
		++cnt[coins[i]];
		if(cnt[coins[i]]==1) t.update(coins[i],coins[i],coins[i]);
		t.update(coins[i]+1,N+1,-coins[i]);
	}
	return t.query(1,N+1)<=1;
}
bool is_happy(int event,int coinsCount,ll coins[]){
	for(int i=0;i<coinsCount;++i){
		if(event==1){
			++cnt[coins[i]];
			if(cnt[coins[i]]==1) t.update(coins[i],coins[i],coins[i]);
			t.update(coins[i]+1,N+1,-coins[i]);
		}else{
			--cnt[coins[i]];
			if(cnt[coins[i]]==0) t.update(coins[i],coins[i],-coins[i]);
			t.update(coins[i]+1,N+1,coins[i]);
		}
	}
	return t.query(1,N+1)<=1;
}
//~ int main()
//~ {
	//~ ios_base::sync_with_stdio(0);
	//~ cout<<init(5,100,{4,8,1,2,16})<<"\n";
	//~ cout<<is_happy(-1,2,{2,8})<<"\n";
	//~ cout<<is_happy(1,3,{7,9,2})<<"\n";
//~ }

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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 9 ms 6044 KB Output is correct
7 Correct 9 ms 6548 KB Output is correct
8 Correct 84 ms 51440 KB Output is correct
9 Correct 84 ms 51908 KB Output is correct
10 Correct 78 ms 50120 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1169 ms 80892 KB Output is correct
7 Correct 1131 ms 80196 KB Output is correct
8 Correct 1189 ms 80928 KB Output is correct
9 Correct 1800 ms 97084 KB Output is correct
10 Correct 1774 ms 103072 KB Output is correct
11 Runtime error 1 ms 468 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 9 ms 6044 KB Output is correct
7 Correct 9 ms 6548 KB Output is correct
8 Correct 84 ms 51440 KB Output is correct
9 Correct 84 ms 51908 KB Output is correct
10 Correct 78 ms 50120 KB Output is correct
11 Correct 1169 ms 80892 KB Output is correct
12 Correct 1131 ms 80196 KB Output is correct
13 Correct 1189 ms 80928 KB Output is correct
14 Correct 1800 ms 97084 KB Output is correct
15 Correct 1774 ms 103072 KB Output is correct
16 Runtime error 1 ms 468 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -