oj.uz

Submission #73372

# Submission time Handle Problem Language Result Execution time Memory
73372 2018-08-28T07:57:51 Z 김세빈(#2270) Happiness (Balkan15_HAPPINESS) C++11
30 / 100
 2000 ms 436104 KB 
#include "happiness.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct node{
	ll v, lz;
	int l, r;
	node() { lz = l = r = 0; v = 1e16; }
};

node T[18181818];
multiset <ll> S;
ll m, allsum;
int tp = 1;

void update(int p)
{
	T[p].v = min(T[T[p].l].v, T[T[p].r].v) + T[p].lz;
}

void spread(int p)
{
	if(T[p].l){
		T[T[p].l].v += T[p].lz;
		T[T[p].l].lz += T[p].lz;
	}
	if(T[p].r){
		T[T[p].r].v += T[p].lz;
		T[T[p].r].lz += T[p].lz;
	}
	T[p].lz = 0;
}

void insert(int p, ll s, ll e, ll v, ll f)
{
	if(s == e){
		T[p].v = f - v + 1;
		T[p].lz = 0;
	}
	else if(v <= (s + e >> 1)){
		spread(p);
		
		if(!T[p].l) T[p].l = ++tp;
		insert(T[p].l, s, (s + e >> 1), v, f);
		
		update(p);
	}
	else{
		spread(p);
		
		if(!T[p].r) T[p].r = ++tp;
		insert(T[p].r, (s + e >> 1) + 1, e, v, f);
		
		update(p);
	}
}

void erase(int p, ll s, ll e, ll v)
{
	if(s == e){
		T[p].v = 1e16;
		T[p].lz = 0;
	}
	else if(v <= (s + e >> 1)){
		spread(p);
		
		erase(T[p].l, s, (s + e >> 1), v);
		
		update(p);
	}
	else{
		spread(p);
		
		erase(T[p].r, (s + e >> 1) + 1, e, v);
		
		update(p);
	}
}

void add_intv(int p, ll s, ll e, ll l, ll r, ll v)
{
	if(!p || e < l || r < s) return;
	if(l <= s && e <= r){
		T[p].v += v;
		T[p].lz += v;
		return;
	}
	
	spread(p);
	
	add_intv(T[p].l, s, (s + e >> 1), l, r, v);
	add_intv(T[p].r, (s + e >> 1) + 1, e, l, r, v);
	
	update(p);
}

ll get_val(int p, ll s, ll e, ll v)
{
	if(s == e) return T[p].v;
	else if(v <= (s + e >> 1)){
		spread(p);
		ll ret = get_val(T[p].l, s, (s + e >> 1), v);
		update(p);
		return ret;
	}
	else{
		spread(p);
		ll ret = get_val(T[p].r, (s + e >> 1) + 1, e, v);
		update(p);
		return ret;
	}
}

bool init(int n, ll M, ll C[])
{
	m = M;
	int i;
	ll s;
	
	sort(C, C + n);
	
	for(i=0; i<n; i++){
		auto it = S.lower_bound(C[i]);
		if(it == S.end() || *it != C[i]){
			if(it == S.end()) s = allsum;
			else s = get_val(1, 1, m, *it) + (*it - 1);
			insert(1, 1, m, C[i], s);
		}
		S.insert(C[i]);
		allsum += C[i];
	}
	
	return T[1].v >= 0;
}

bool is_happy(int t, int n, ll C[])
{
	int i;
	ll s;
	
	for(i=0; i<n; i++){
		if(t == 1){
			auto it = S.lower_bound(C[i]);
			if(it == S.end() || *it != C[i]){
				if(it == S.end()) s = allsum;
				else s = get_val(1, 1, m, *it) + (*it - 1);
				insert(1, 1, m, C[i], s);
			}
			S.insert(C[i]);
			allsum += C[i];
			
			add_intv(1, 1, m, C[i] + 1, m, C[i]);
		}
		else{
			auto it = S.lower_bound(C[i]);
			
			if(next(it) == S.end() || *next(it) != C[i]){
				erase(1, 1, m, C[i]);
			}
			
			S.erase(it);
			allsum -= C[i];
			add_intv(1, 1, m, C[i] + 1, m, -C[i]);
		}
	}
	
	return T[1].v >= 0;
}

Compilation message

happiness.cpp: In function 'void insert(int, ll, ll, ll, ll)':
happiness.cpp:44:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else if(v <= (s + e >> 1)){
                ~~^~~
happiness.cpp:48:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   insert(T[p].l, s, (s + e >> 1), v, f);
                      ~~^~~
happiness.cpp:56:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   insert(T[p].r, (s + e >> 1) + 1, e, v, f);
                   ~~^~~
happiness.cpp: In function 'void erase(int, ll, ll, ll)':
happiness.cpp:68:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else if(v <= (s + e >> 1)){
                ~~^~~
happiness.cpp:71:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   erase(T[p].l, s, (s + e >> 1), v);
                     ~~^~~
happiness.cpp:78:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   erase(T[p].r, (s + e >> 1) + 1, e, v);
                  ~~^~~
happiness.cpp: In function 'void add_intv(int, ll, ll, ll, ll, ll)':
happiness.cpp:95:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  add_intv(T[p].l, s, (s + e >> 1), l, r, v);
                       ~~^~~
happiness.cpp:96:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  add_intv(T[p].r, (s + e >> 1) + 1, e, l, r, v);
                    ~~^~~
happiness.cpp: In function 'll get_val(int, ll, ll, ll)':
happiness.cpp:104:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else if(v <= (s + e >> 1)){
                ~~^~~
happiness.cpp:106:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll ret = get_val(T[p].l, s, (s + e >> 1), v);
                                ~~^~~
happiness.cpp:112:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll ret = get_val(T[p].r, (s + e >> 1) + 1, e, v);
                             ~~^~~
grader.cpp: In function 'int main()':
grader.cpp:14:9: warning: unused variable 'd' [-Wunused-variable]
  int i, d;
         ^
grader.cpp:15:12: warning: unused variable 'max_code' [-Wunused-variable]
  long long max_code;
            ^~~~~~~~
grader.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~~
grader.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &coins[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~
grader.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
grader.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &ck, &c);
   ~~~~~^~~~~~~~~~~~~~~~~
grader.cpp:28:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld", &A[j]);
    ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 427260 KB Output is correct
2 Correct 341 ms 427364 KB Output is correct
3 Correct 347 ms 427364 KB Output is correct
4 Correct 352 ms 427400 KB Output is correct
5 Correct 332 ms 427448 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 427652 KB Output is correct
2 Correct 327 ms 427700 KB Output is correct
3 Correct 353 ms 428120 KB Output is correct
4 Correct 388 ms 428260 KB Output is correct
5 Correct 385 ms 428272 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1370 ms 433412 KB Output is correct
2 Correct 1047 ms 433412 KB Output is correct
3 Correct 1242 ms 433548 KB Output is correct
4 Correct 1975 ms 433548 KB Output is correct
5 Execution timed out 2109 ms 436104 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 436104 KB Time limit exceeded
2 Halted 0 ms 0 KB -