oj.uz

Submission #598649

# Submission time Handle Problem Language Result Execution time Memory
598649 2022-07-18T16:02:57 Z CaroLinda Weirdtree (RMI21_weirdtree) C++14
5 / 100
 9 ms 2852 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>

//solving for k == 1

#define ll long long

const int MAXN = 1010;

using namespace std;

int N, Q;
int arr[MAXN];

void initialise(int n, int q, int h[]) {
	N = n;
	Q = q;

	for(int i = 1; i <= N; i++)
		arr[i] = h[i];
}
void cut(int l, int r, int k) {

	vector<pair<int,int> > vec;

	for(int i = l ; i <= r; i++){
		vec.push_back(make_pair(arr[i],-i));
	}

	sort(vec.begin(), vec.end());

	ll s = 0;
	int qtd = 0;

	for(int i = vec.size()-1; i >= 0; i--){
		qtd++;
		s += vec[i].first;

		ll ant = (i == 0) ? 0 : vec[i-1].first;

		if(s-ant * qtd < k)
			continue;

		ll x = (s-k+qtd-1)/(ll)qtd;

		for(int j = i; j < vec.size(); j++){
			int id = -vec[j].second;
			k -= arr[id]-x;
			arr[id] = x;
		}


		if(x == 0 || k == 0)
			return;

		for(int j = vec.size()-1; j >= 0 && k; j--, k--)
			arr[-vec[j].second]--;

		return;
	}

	for(int i = l ; i <= r; i++)
		arr[i] = 0;
}
void magic(int i, int x) {
	arr[i] = x;
}
long long int inspect(int l, int r) {
	ll s = 0;
	for(int i = l; i <= r; i++)
		s += arr[i];
	return s;
}

Compilation message

weirdtree.cpp: In function 'void cut(int, int, int)':
weirdtree.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(int j = i; j < vec.size(); j++){
      |                  ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 6 ms 368 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 6 ms 368 KB Output is correct
3 Runtime error 3 ms 1236 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 19.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 2852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 6 ms 368 KB Output is correct
3 Runtime error 3 ms 1236 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 6 ms 368 KB Output is correct
3 Runtime error 3 ms 1236 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -