Hi,
I have been working on this problem for a while and can’t fix test cases 6 and 9 (Wrong Answer). What’s is wrong?
#include <bits/stdc++.h>
using namespace std;
struct Change {
int day, cow, change;
bool operator < (const Change& other) const {
if (day < other.day) {
return true;
}
else if (day > other.day) {
return false;
}
if (cow < other.cow) {
return true;
}
return cow == other.cow && change < other.change;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
freopen("measurement.in", "r", stdin);
freopen("measurement.out", "w", stdout);
int length, initial;
cin >> length >> initial;
vector<Change> changes(length);
unordered_map<int, int> values = {{0, initial}};
map<int, unordered_set<int>> inverse = {{initial, unordered_set<int>{0}}};
for (Change &change: changes) {
cin >> change.day >> change.cow >> change.change;
values[change.cow] = initial;
inverse[initial].insert(change.cow);
}
sort(changes.begin(), changes.end());
int highest_changes = 0;
int leading_value = initial;
for (Change &change: changes) {
int value = values[change.cow] + change.change;
unordered_set<int> &leaders = inverse[leading_value];
if (leaders.find(change.cow) != leaders.end()) {
if (change.change < 0) {
auto it = inverse.rbegin();
it--;
if (value <= (*it).first) {
highest_changes++;
if (leaders.size() == 1) {
leading_value = (*it).first;
}
}
else {
leading_value = value;
}
}
else {
if (leaders.size() > 1) {
highest_changes++;
}
leading_value = value;
}
}
else if (value >= leading_value) {
highest_changes++;
leading_value = value;
}
inverse[values[change.cow]].erase(change.cow);
if (inverse[values[change.cow]].empty()) {
inverse.erase(values[change.cow]);
}
values[change.cow] = value;
inverse[value].insert(change.cow);
}
cout << highest_changes << "\n";
return 0;
}