oj.uz

Submission #73279

# Submission time Handle Problem Language Result Execution time Memory
73279 2018-08-28T06:34:02 Z 김세빈(#2270) Happiness (Balkan15_HAPPINESS) C++11
30 / 100
 2000 ms 5316 KB 
#include "happiness.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

ll m, q, g;
ll sz = 400;

struct bucket{
	vector <pll> V;
	ll r, mv, sum;
	
	bucket() { r = sum = 0, mv = m; }
	
	void insert(ll v)
	{
		ll i, s = 0;
		
		sum += v;
		mv = m;
		
		for(pll &p: V){
			if(p.first > v) p.second += v;
			else if(p.first < v) s += p.first;
			mv = min(mv, p.second);
		}
		
		V.push_back(pll(v, s - v + 1));
		
		mv = min(mv, s - v + 1);
		r = max(v, r);
	}
	
	void erase(ll v)
	{
		ll i, f, x;
		
		sum -= v;
		i = f = 0; mv = m;
		r = 0;
		
		for(pll &p: V){
			if(p.first > v) p.second -= v;
			if(f == 0 && p.first == v) x = i, f = 1;
			else{
				mv = min(mv, p.second);
				r = max(p.first, r);
			}
			i ++;
		}
		
		swap(V[x], V.back()); V.pop_back();
	}
};

bucket B[555];

bool check()
{
	ll i, s;
	
	for(i=0, s=0; i<=g; i++){
		if(s + B[i].mv < 0) return 0;
		s += B[i].sum; 
	}
	
	return 1;
}

void refresh()
{
	vector <ll> V;
	ll i;
	
	for(i=0; i<=g; i++){
		for(pll &p: B[i].V) V.push_back(p.first);
		B[i].V.clear(); B[i].sum = 0, B[i].r = 0; B[i].mv = m;
	}
	
	sort(V.begin(), V.end());
	
	for(i=0; i<V.size(); i++){
		B[i / sz].insert(V[i]);
	}
	g = (V.size() - 1) / sz;
}

bool init(int n, ll M, ll C[])
{
	m = M;
	
	int i;
	
	sort(C, C + n);
	
	for(i=0; i<n; i++){
		B[i / sz].insert(C[i]);
	}
	g = (n - 1) / sz;
	
	return check();
}

bool is_happy(int t, int n, ll C[])
{
	int i, j;
	
	for(i=0; i<n; i++){
		for(j=0; j<=g; j++){
			if(C[i] <= B[j].r) break;
		}
		if(t == 1){
			if(j > g) g = j;
			B[j].insert(C[i]);
		}
		else B[j].erase(C[i]);
	}
	
	if(++q > sz) refresh(), q = 0;
	
	return check();
}

Compilation message

happiness.cpp: In member function 'void bucket::insert(ll)':
happiness.cpp:21:6: warning: unused variable 'i' [-Wunused-variable]
   ll i, s = 0;
      ^
happiness.cpp: In function 'void refresh()':
happiness.cpp:86:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<V.size(); i++){
           ~^~~~~~~~~
happiness.cpp: In function 'bool is_happy(int, int, ll*)':
happiness.cpp:56:11: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   swap(V[x], V.back()); V.pop_back();
           ^
happiness.cpp:40:12: note: 'x' was declared here
   ll i, f, x;
            ^
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 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 3 ms 520 KB Output is correct
5 Correct 3 ms 604 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 720 KB Output is correct
2 Correct 4 ms 720 KB Output is correct
3 Correct 26 ms 1000 KB Output is correct
4 Correct 29 ms 1000 KB Output is correct
5 Correct 27 ms 1000 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 40.0

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