#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
const int MAX_N = 100;
struct MedianStructure {
set<pair<int, int> > data;
set<pair<int, int> >::iterator median;
long long sumdists;
MedianStructure() {
sumdists = 0LL;
median = data.end();
}
void moveMedian(int dir) {
sumdists -= dir * median->first;
if(dir == 1)
median++;
else
median--;
sumdists -= dir * median->first;
}
void insert(int val, int poz) {
pair<int, int> x = make_pair(val, poz);
data.insert(x);
if(data.size() == 1)
median = data.begin();
else if(x < *median) {
sumdists -= val;
if(data.size() % 2 == 0) moveMedian(-1);
} else {
sumdists += val;
if(data.size() % 2 == 1) moveMedian(+1);
}
}
void erase(int val, int poz) {
pair<int, int> x = make_pair(val, poz);
if(x < *median) {
sumdists += val;
data.erase(x);
if(data.size() % 2 == 1) moveMedian(1);
} else if(x > *median) {
sumdists -= val;
if(data.size() % 2 == 1) moveMedian(-1);
data.erase(x);
} else if(data.size() % 2 == 0) {
moveMedian(1);
data.erase(x);
sumdists += val;
} else {
moveMedian(-1);
data.erase(x);
sumdists -= val;
}
}
long long getmediansum() {
return sumdists - median->first * (1 - data.size() % 2);
}
};
int besthub(int R, int L, int X[], long long B) {
int l;
int rez = 1;
MedianStructure *med = new MedianStructure();
// X[l...r] works
l = 0;
for(int r = 0; r < R; ++r) {
med->insert(X[r], r);
while(l < r && med->getmediansum() > B) {
med->erase(X[l], l);
l++;
}
rez = max(rez, r - l + 1);
}
return rez;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
3 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
256 KB |
Output is correct |
| 9 |
Correct |
2 ms |
256 KB |
Output is correct |
| 10 |
Correct |
3 ms |
256 KB |
Output is correct |
| 11 |
Correct |
2 ms |
384 KB |
Output is correct |
| 12 |
Correct |
3 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
2 ms |
384 KB |
Output is correct |
| 15 |
Correct |
2 ms |
256 KB |
Output is correct |
| 16 |
Correct |
2 ms |
256 KB |
Output is correct |
| 17 |
Correct |
2 ms |
384 KB |
Output is correct |
| 18 |
Correct |
2 ms |
256 KB |
Output is correct |
| 19 |
Correct |
2 ms |
384 KB |
Output is correct |
| 20 |
Correct |
2 ms |
256 KB |
Output is correct |
| 21 |
Correct |
2 ms |
256 KB |
Output is correct |
| 22 |
Correct |
2 ms |
256 KB |
Output is correct |
| 23 |
Correct |
2 ms |
384 KB |
Output is correct |
| 24 |
Correct |
2 ms |
412 KB |
Output is correct |
| 25 |
Correct |
2 ms |
384 KB |
Output is correct |
| 26 |
Correct |
1 ms |
304 KB |
Output is correct |
| 27 |
Correct |
3 ms |
384 KB |
Output is correct |
| 28 |
Correct |
3 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
304 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
3 ms |
256 KB |
Output is correct |
| 6 |
Correct |
3 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
3 ms |
256 KB |
Output is correct |
| 10 |
Correct |
2 ms |
256 KB |
Output is correct |
| 11 |
Correct |
3 ms |
256 KB |
Output is correct |
| 12 |
Correct |
3 ms |
256 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
3 ms |
384 KB |
Output is correct |
| 15 |
Correct |
2 ms |
384 KB |
Output is correct |
| 16 |
Correct |
2 ms |
384 KB |
Output is correct |
| 17 |
Correct |
3 ms |
384 KB |
Output is correct |
| 18 |
Correct |
2 ms |
384 KB |
Output is correct |
| 19 |
Correct |
2 ms |
384 KB |
Output is correct |
| 20 |
Correct |
2 ms |
384 KB |
Output is correct |
| 21 |
Correct |
3 ms |
384 KB |
Output is correct |
| 22 |
Correct |
4 ms |
384 KB |
Output is correct |
| 23 |
Correct |
4 ms |
640 KB |
Output is correct |
| 24 |
Correct |
4 ms |
512 KB |
Output is correct |
| 25 |
Correct |
4 ms |
512 KB |
Output is correct |
| 26 |
Correct |
4 ms |
640 KB |
Output is correct |
| 27 |
Correct |
4 ms |
512 KB |
Output is correct |
| 28 |
Correct |
4 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
512 KB |
Output is correct |
| 2 |
Correct |
7 ms |
512 KB |
Output is correct |
| 3 |
Correct |
41 ms |
5780 KB |
Output is correct |
| 4 |
Correct |
43 ms |
6520 KB |
Output is correct |
| 5 |
Correct |
14 ms |
896 KB |
Output is correct |
| 6 |
Correct |
15 ms |
896 KB |
Output is correct |
| 7 |
Correct |
38 ms |
6136 KB |
Output is correct |
| 8 |
Correct |
42 ms |
6136 KB |
Output is correct |
| 9 |
Correct |
19 ms |
1148 KB |
Output is correct |
| 10 |
Correct |
18 ms |
1024 KB |
Output is correct |
| 11 |
Correct |
41 ms |
6544 KB |
Output is correct |
| 12 |
Correct |
53 ms |
6520 KB |
Output is correct |
| 13 |
Correct |
17 ms |
896 KB |
Output is correct |
| 14 |
Correct |
16 ms |
896 KB |
Output is correct |
| 15 |
Correct |
34 ms |
4856 KB |
Output is correct |
| 16 |
Correct |
33 ms |
4924 KB |
Output is correct |
| 17 |
Correct |
50 ms |
5752 KB |
Output is correct |
| 18 |
Correct |
44 ms |
5752 KB |
Output is correct |
| 19 |
Correct |
45 ms |
6172 KB |
Output is correct |
| 20 |
Correct |
41 ms |
6136 KB |
Output is correct |
