oj.uz

Submission #73334

# Submission time Handle Problem Language Result Execution time Memory
73334 2018-08-28T07:32:54 Z 김세빈(#2270) Happiness (Balkan15_HAPPINESS) C++11
30 / 100
 2000 ms 480928 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[20202020];
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].l].lz, T[T[p].r].v + T[T[p].r].lz);
	T[p].lz = 0;
}

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

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].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 + T[p].lz;
	else if(v <= (s + e >> 1)){
		return get_val(T[p].l, s, (s + e >> 1), v) + T[p].lz;
	}
	else{
		return get_val(T[p].r, (s + e >> 1) + 1, e, v) + T[p].lz;
	}
}

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 + T[1].lz >= 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]);
			S.erase(it);
			allsum -= C[i];
			
			it = S.lower_bound(C[i]);
			if(it == S.end() || *it != C[i]){
				erase(1, 1, m, C[i]);
			}
			add_intv(1, 1, m, C[i] + 1, m, -C[i]);
		}
	}
	
	return T[1].v + T[1].lz >= 0;
}

Compilation message

happiness.cpp: In function 'void insert(int, ll, ll, ll, ll)':
happiness.cpp:38:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else if(v <= (s + e >> 1)){
                ~~^~~
happiness.cpp:42:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   insert(T[p].l, s, (s + e >> 1), v, f);
                      ~~^~~
happiness.cpp:50: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:62:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else if(v <= (s + e >> 1)){
                ~~^~~
happiness.cpp:65:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   erase(T[p].l, s, (s + e >> 1), v);
                     ~~^~~
happiness.cpp:72: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:88:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  add_intv(T[p].l, s, (s + e >> 1), l, r, v);
                       ~~^~~
happiness.cpp:89: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:97:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else if(v <= (s + e >> 1)){
                ~~^~~
happiness.cpp:98:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   return get_val(T[p].l, s, (s + e >> 1), v) + T[p].lz;
                              ~~^~~
happiness.cpp:101:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   return get_val(T[p].r, (s + e >> 1) + 1, e, v) + T[p].lz;
                           ~~^~~
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 368 ms 474744 KB Output is correct
2 Correct 379 ms 474852 KB Output is correct
3 Correct 475 ms 474852 KB Output is correct
4 Correct 381 ms 474972 KB Output is correct
5 Correct 369 ms 474972 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 475032 KB Output is correct
2 Correct 397 ms 475032 KB Output is correct
3 Correct 455 ms 475600 KB Output is correct
4 Correct 526 ms 475600 KB Output is correct
5 Correct 440 ms 475672 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1250 ms 480784 KB Output is correct
2 Correct 1291 ms 480784 KB Output is correct
3 Correct 1337 ms 480900 KB Output is correct
4 Execution timed out 2119 ms 480928 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

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