oj.uz

Submission #73326

# Submission time Handle Problem Language Result Execution time Memory
73326 2018-08-28T07:21:06 Z 김세빈(#2270) Happiness (Balkan15_HAPPINESS) C++11
60 / 100
 1533 ms 521748 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[16606060];
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[T[p].l].s) T[T[p].l].lz += T[p].lz;
	if(T[T[p].r].s) 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].lz = 0;
		}
		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:41:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else if(v <= (s + e >> 1)){
                ~~^~~
happiness.cpp:45:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   insert(T[p].l, s, (s + e >> 1), v, f);
                      ~~^~~
happiness.cpp:53: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 'll get_sum(int, ll, ll, ll, ll)':
happiness.cpp:91: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:91: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:108:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  add_intv(T[p].l, s, (s + e >> 1), l, r, v);
                       ~~^~~
happiness.cpp:109: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 520404 KB Output is correct
2 Correct 385 ms 520404 KB Output is correct
3 Correct 371 ms 520492 KB Output is correct
4 Correct 374 ms 520492 KB Output is correct
5 Correct 386 ms 520492 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 520492 KB Output is correct
2 Correct 446 ms 520556 KB Output is correct
3 Correct 437 ms 520672 KB Output is correct
4 Correct 402 ms 520672 KB Output is correct
5 Correct 410 ms 520672 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 975 ms 521608 KB Output is correct
2 Correct 958 ms 521688 KB Output is correct
3 Correct 925 ms 521688 KB Output is correct
4 Correct 1419 ms 521688 KB Output is correct
5 Correct 1383 ms 521688 KB Output is correct
6 Correct 909 ms 521688 KB Output is correct
7 Correct 872 ms 521688 KB Output is correct

Subtask #4
0 / 40.0

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