# USACO Silver: Triangle overflow?

Hello everyone! I have tried to solve USACO 2020 February Contest, Silver Problem 2. Triangles.
Conceptually I understand how to solve it, in fact my solution passes first 6 testcases, where \ n <= 40000, but starting with 7th testcase, where \ n >= 60000 it doesn’t work.

My guess is that it overflows long long at some point when I count xsum and ysum, but I have put mod any place possible and it didn’t work. The only difference my code has comparing to official solution is the way I count xsum and ysum for each point. I have also tried my solution with maps, but it gave the same result.

So I create prefix array and suffix array. Prefix array to count xsum to the left of pivot point and suffix array to count xsum to the right of pivot point. The same thing with y-coordinates.

``````#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <queue>
#include <unordered_map>

using namespace std;
using ll = long long;

void IO(string File_name) {
cin.tie(0)->sync_with_stdio(0);
if(File_name.size()) {
freopen((File_name + ".in").c_str(), "r", stdin);
freopen((File_name + ".out").c_str(), "w", stdout);
}
}

const ll mod = 1e9 + 7;
const ll MAX_C = 1e4;
const ll MAX_N = 1e5;

struct fence{
ll x, y;
ll xsum = 0;
ll ysum = 0;
};

fence v[MAX_N];
vector<pair<ll, ll>> XY[2 * MAX_C + 1], YX[2 * MAX_C + 1];

void sol() {
ll n;
cin >> n;

for(ll i = 0; i < n; i++) {
cin >> v[i].x >> v[i].y;
XY[v[i].x + MAX_C].push_back({v[i].y, i});
YX[v[i].y + MAX_C].push_back({v[i].x, i});
}

for(ll y = 0; y < 2 * MAX_C + 1; y++){
vector<pair<ll, ll>> el = YX[y];
if(el.size() < 2) continue;

sort(el.begin(), el.end());

ll N = (ll) el.size();

vector<ll> diffs(N - 1);

// compute diffs array to know diffs between adjacent elements.
for(ll i = 0; i < N - 1; i++){
diffs[i] = el[i + 1].first - el[i].first;
}
vector<ll> pref(N), suf(N);

/* after this loop vector pref will contain all diffs between
the first element and any other one.*/
for(ll i = 1; i < N; i++){
pref[i] = (pref[i - 1] + diffs[i - 1]);
}
// here I compute xsum by hand
for(ll i = 1; i < N; i++){
pref[i] = pref[i] + pref[i - 1];
v[el[i].second].xsum = pref[i];
}
/* after this loop vector suf will contain all diffs between
the last element and any other one.*/
for(ll i = N - 2; i >= 0; i--){
suf[i] = suf[i + 1] + diffs[i];
}
// here I compute xsum by hand
for(ll i = N - 2; i >= 0; i--){
suf[i] = suf[i] + suf[i + 1];
v[el[i].second].xsum += suf[i];
}
}

for(ll x = 0; x < 2 * MAX_C + 1; x++){
vector<pair<ll, ll>> el = XY[x];
if(el.size() < 2) continue;

sort(el.begin(), el.end());

ll N = (ll) el.size();
// compute diffs array to know diffs between adjacent elements.
vector<ll> diffs(N - 1);

for(ll i = 0; i < N - 1; i++){
diffs[i] = el[i + 1].first - el[i].first;
}
vector<ll> pref(N), suf(N);
/* after this loop vector pref will contain all diffs between
the first element and any other one.*/
for(ll i = 1; i < N; i++){
pref[i] = (pref[i - 1] + diffs[i - 1]);
}
// here I compute ysum by hand
for(ll i = 1; i < N; i++){
pref[i] = pref[i] + pref[i - 1];
v[el[i].second].ysum = pref[i];
}
/* after this loop vector suf will contain all diffs between
the last element and any other one.*/
for(ll i = N - 2; i >= 0; i--){
suf[i] = (suf[i + 1] + diffs[i]);
}
// here I compute ysum by hand
for(ll i = N - 2; i >= 0; i--){
suf[i] = suf[i] + suf[i + 1];
v[el[i].second].ysum += suf[i];
}
}
ll sum = 0;
for(ll i = 0; i < n; i++){
sum += (v[i].xsum * v[i].ysum) % mod;
sum %= mod;
}
cout << sum;
}

int main() {
IO("triangles");
ll T = 1;
//cin >> T;
while(T--) sol();
return 0;
}

``````

Embarrassingly, the test data for this problem is very weak; your solution shouldn’t actually pass any of the test cases aside from the sample.

Try stress testing as suggested below: