This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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--;
}
}
if (cnt == 0) return 0;
return w[cnt-1];
}
#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);
killit(res);
return res;
}
int Maid(int w){
if(w>m) return -1;
int index = getit(w);
return v[index].second;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |