Diamond Collector USACO 2016 Silver US Open #2 Help

Problem Info

Diamond Collector https://usaco.org/index.php?page=viewproblem2&cpid=643

What I’ve Tried

Before reading the official 2-pointers solution, I came up with a solution of O(N*logN), where I check for each index i how many diamonds can fit with it. To prevent overlapping, I used regions so that if i is within the maximum case in the region, it will check if it can replace it and make a new region. I can’t really think of anything wrong with my current solution. If my approach is possibly valid with some fixes, I would appreciate if anyone could check for me.

Code

``````using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define forr(i,a,b) for (int i = (int)(a); i < (int)(b); ++i)
#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int n,k;
void solve() {
cin >> n >> k;
vector<int> v(n);
forr(i,0,n) {
cin >> v[i];
}
sort(v.begin(),v.end());
int ans1 = 0, ans2 = 0;
int startind=0, endind=0, maxinregion = 0;
bool inregion = false;
forr(i,0,n) {
auto it = upper_bound(v.begin(),v.end(),v[i]+k )-1;
int upper = distance(v.begin(),it); // last index possible
if(i<=endind) { // check if in current region
if(upper-i+1 > maxinregion) {
maxinregion = upper-i+1;
startind = i, endind = upper;
if(maxinregion>ans1) {
if(!inregion) ans2 = ans1;
ans1 = maxinregion;
inregion = true;
}else if (maxinregion>ans2) {
ans2 = maxinregion;
}
}
}else { // new region
inregion = false;
maxinregion = upper-i+1;
endind = upper;
if(maxinregion>ans1) {
ans2 = ans1;
ans1 = maxinregion;
inregion = true;
}else if (maxinregion>ans2) {
ans2 = maxinregion;
}
}
}
cout << ans1 + ans2;
}

int main() {
FASTIO;
solve();
return 0;
}
``````