oj.uz

Submission #73321

# Submission time Handle Problem Language Result Execution time Memory
73321 2018-08-28T07:17:13 Z 김세빈(#2270) Happiness (Balkan15_HAPPINESS) C++11
0 / 100
 1311 ms 317776 KB 
#include "happiness.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

node T[10101010];
ll m;
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;
	T[p].s = T[T[p].l].s + T[T[p].r].s;
}

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){
		if(T[p].s == 0) T[p].v = f - v + 1;
		T[p].s += v;
	}
	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].s -= v;
		if(T[p].s == 0){
			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);
	}
}

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

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);
}

bool init(int n, ll M, ll C[])
{
	m = M;
	int i;
	ll s;
	
	sort(C, C + n);
	
	for(i=0; i<n; i++){
		s = get_sum(1, 1, m, 1, C[i] - 1);
		insert(1, 1, m, C[i], s);
	}
	
	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){
			s = get_sum(1, 1, m, 1, C[i] - 1);
			insert(1, 1, m, C[i], s);
			add_intv(1, 1, m, C[i] + 1, m, C[i]);
		}
		else{
			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:65:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else if(v <= (s + e >> 1)){
                ~~^~~
happiness.cpp:68:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   erase(T[p].l, s, (s + e >> 1), v);
                     ~~^~~
happiness.cpp:75:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   erase(T[p].r, (s + e >> 1) + 1, e, v);
                  ~~^~~
happiness.cpp: In function 'll get_sum(int, ll, ll, ll, ll)':
happiness.cpp:88:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll ret = get_sum(T[p].l, s, (s + e >> 1), l, r) + get_sum(T[p].r, (s + e >> 1) + 1, e, l, r);
                               ~~^~~
happiness.cpp:88:71: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll ret = get_sum(T[p].l, s, (s + e >> 1), l, r) + get_sum(T[p].r, (s + e >> 1) + 1, e, l, r);
                                                                     ~~^~~
happiness.cpp: In function 'void add_intv(int, ll, ll, ll, ll, ll)':
happiness.cpp:105:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  add_intv(T[p].l, s, (s + e >> 1), l, r, v);
                       ~~^~~
happiness.cpp:106:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  add_intv(T[p].r, (s + e >> 1) + 1, e, l, r, 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 316692 KB Output is correct
2 Correct 230 ms 316692 KB Output is correct
3 Incorrect 240 ms 316756 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 316756 KB Output is correct
2 Correct 237 ms 316836 KB Output is correct
3 Incorrect 267 ms 316876 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 762 ms 317776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1311 ms 317776 KB Output isn't correct
2 Halted 0 ms 0 KB -