oj.uz

Submission #151005

# Submission time Handle Problem Language Result Execution time Memory
151005 2019-09-01T14:26:20 Z pichulia King of Chairs (FXCUP4_chairs) C++17
100 / 100
 135 ms 10004 KB 
#include "king.h"
#include<algorithm>
using namespace std;

long long SendInfo(std::vector<int> w, std::vector<int> c) {
	int n = w.size();
	sort(w.begin(), w.end());
	sort(c.begin(), c.end());
	int cnt = 0;
	int i, j;
	for (i = j = n - 1; i >= 0 && j >= 0;)
	{
		if (w[i] > c[j]) i--;
		else if (w[i] <= c[j]) {
			cnt++;
			i--;
			j--;
		}
	}return 0;
}

#include "vassal.h"
#include<algorithm>
using namespace std;
#define I 131072
long long m;
int n;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
pii v[100009];
int mx[2 * I];
int cnt;
void Init(long long mm, std::vector<int> c){
	n = c.size();
	m = mm;
	// ToDo
	for (int i = 0; i < n; i++) {
		v[i].first = c[i];
		v[i].second = i;
	}
	cnt = 0;
	sort(v, v + n);
	for (int i = 0; i < n; i++) {
		mx[i + I] = i;
	}
	for (int i = n; i < I; i++) {
		mx[i + I] = I;
	}
	for (int i = I - 1; i > 0; i--) {
		mx[i] = min(mx[i * 2], mx[i * 2 + 1]);
	}
}
int gett(int dep, int ql, int qr, int ll, int rr)
{
	if (ql <= ll && rr <= qr) { return mx[dep]; }
	if (ll > qr || ql > rr) return I;
	return min(gett(dep * 2, ql, qr, ll, (ll + rr) / 2), gett(dep * 2 + 1, ql, qr, (ll + rr) / 2 + 1, rr));
}
void killit(int i)
{
	i = i + I;
	mx[i] = I;
	i /= 2;
	while (i > 0)
	{
		mx[i] = min(mx[i * 2], mx[i * 2 + 1]);
		i /= 2;
	}
}
int getit(int w)
{
	int base = lower_bound(v, v + n, pii(w, -1)) - v;
	int res = gett(1, base, I - 1, 0, I - 1);
	return res;
}

int Maid(int w){
	//if(m<n && w>v[m].first)	return -1;
	int index = getit(w);
	if (index == I) return -1;
	killit(index);
	return v[index].second;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1788 KB Correct
2 Correct 5 ms 1808 KB Correct
3 Correct 5 ms 1660 KB Correct
4 Correct 5 ms 1660 KB Correct
5 Correct 5 ms 1788 KB Correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6024 KB Correct
2 Correct 94 ms 9336 KB Correct
3 Correct 100 ms 9992 KB Correct
4 Correct 102 ms 9912 KB Correct
5 Correct 103 ms 9828 KB Correct
6 Correct 103 ms 9828 KB Correct
7 Correct 100 ms 9988 KB Correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 6156 KB Correct
2 Correct 122 ms 9240 KB Correct
3 Correct 127 ms 9872 KB Correct
4 Correct 132 ms 9872 KB Correct
5 Correct 135 ms 9936 KB Correct
6 Correct 134 ms 10004 KB Correct
7 Correct 127 ms 10000 KB Correct
8 Correct 99 ms 9960 KB Correct