Submission #73367

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
73367	2018-08-28T07:55:22 Z	김세빈(#2270)	Happiness (Balkan15_HAPPINESS)	C++11	30 / 100	2000 ms	480816 KB

happiness

#include "happiness.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

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

void update(node *p)
{
	p -> v = min(p -> l? p -> l -> v : 1e16, p -> r? p -> r -> v : 1e16) + p -> lz;
}

void spread(node *p)
{
	if(p -> l){
		p -> l -> v += p -> lz;
		p -> l -> lz += p -> lz;
	}
	if(p -> r){
		p -> r -> v += p -> lz;
		p -> r -> lz += p -> lz;
	}
	p -> lz = 0;
}

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

void erase(node *p, ll s, ll e, ll v)
{
	if(s == e){
		p -> v = 1e16;
		p -> lz = 0;
	}
	else if(v <= (s + e >> 1)){
		spread(p);
		
		erase(p -> l, s, (s + e >> 1), v);
		
		update(p);
	}
	else{
		spread(p);
		
		erase(p -> r, (s + e >> 1) + 1, e, v);
		
		update(p);
	}
}

void add_intv(node *p, ll s, ll e, ll l, ll r, ll v)
{
	if(!p || e < l || r < s) return;
	if(l <= s && e <= r){
		p -> v += v;
		p -> lz += v;
		return;
	}
	
	spread(p);
	
	add_intv(p -> l, s, (s + e >> 1), l, r, v);
	add_intv(p -> r, (s + e >> 1) + 1, e, l, r, v);
	
	update(p);
}

ll get_val(node *p, ll s, ll e, ll v)
{
	if(s == e) return p -> v;
	else if(v <= (s + e >> 1)){
		spread(p);
		ll ret = get_val(p -> l, s, (s + e >> 1), v);
		update(p);
		return ret;
	}
	else{
		spread(p);
		ll ret = get_val(p -> r, (s + e >> 1) + 1, e, v);
		update(p);
		return ret;
	}
}

bool init(int n, ll M, ll C[])
{
	m = M;
	int i, j;
	ll s;
	
	r = (T + 1);
	
	sort(C, C + n);
	
	for(i=0, j=0; i<n; i++){
		for(; j<n && C[j] < C[i]; j++) s += C[j];
		insert(r, 1, m, C[i], s);
		S.insert(C[i]);
		allsum += C[i];
	}
	
	return r -> 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(r, 1, m, *it) + (*it - 1);
				insert(r, 1, m, C[i], s);
			}
			S.insert(C[i]);
			allsum += C[i];
			
			add_intv(r, 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(r, 1, m, C[i]);
			}
			
			S.erase(it);
			allsum -= C[i];
			
			add_intv(r, 1, m, C[i] + 1, m, -C[i]);
		}
	}
	
	return r -> v >= 0;
}

Compilation message

happiness.cpp: In function 'void insert(node*, ll, ll, ll, ll)':
happiness.cpp:45:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else if(v <= (s + e >> 1)){
                ~~^~~
happiness.cpp:49:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   insert(p -> l, s, (s + e >> 1), v, f);
                      ~~^~~
happiness.cpp:57:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   insert(p -> r, (s + e >> 1) + 1, e, v, f);
                   ~~^~~
happiness.cpp: In function 'void erase(node*, ll, ll, ll)':
happiness.cpp:69:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else if(v <= (s + e >> 1)){
                ~~^~~
happiness.cpp:72:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   erase(p -> l, s, (s + e >> 1), v);
                     ~~^~~
happiness.cpp:79:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   erase(p -> r, (s + e >> 1) + 1, e, v);
                  ~~^~~
happiness.cpp: In function 'void add_intv(node*, ll, ll, ll, ll, ll)':
happiness.cpp:96:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  add_intv(p -> l, s, (s + e >> 1), l, r, v);
                       ~~^~~
happiness.cpp:97:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  add_intv(p -> r, (s + e >> 1) + 1, e, l, r, v);
                    ~~^~~
happiness.cpp: In function 'll get_val(node*, ll, ll, ll)':
happiness.cpp:105:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else if(v <= (s + e >> 1)){
                ~~^~~
happiness.cpp:107:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll ret = get_val(p -> l, s, (s + e >> 1), v);
                                ~~^~~
happiness.cpp:113:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll ret = get_val(p -> r, (s + e >> 1) + 1, e, v);
                             ~~^~~
happiness.cpp: In function 'bool init(int, ll, ll*)':
happiness.cpp:130:36: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   for(; j<n && C[j] < C[i]; j++) s += C[j];
                                  ~~^~~~~~~
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	382 ms	474692 KB	Output is correct
2	Correct	350 ms	474704 KB	Output is correct
3	Correct	361 ms	474848 KB	Output is correct
4	Correct	381 ms	474848 KB	Output is correct
5	Correct	344 ms	474868 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	400 ms	474992 KB	Output is correct
2	Correct	396 ms	474992 KB	Output is correct
3	Correct	408 ms	475432 KB	Output is correct
4	Correct	506 ms	475432 KB	Output is correct
5	Correct	394 ms	475532 KB	Output is correct

Subtask #3

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1080 ms	480704 KB	Output is correct
2	Correct	1299 ms	480744 KB	Output is correct
3	Correct	1245 ms	480744 KB	Output is correct
4	Execution timed out	2075 ms	480816 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	2041 ms	480816 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-