USACO Silver: Triangle overflow?

Debugging Help
#1

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.

msedge_g4f1zNbXkd
msedge_g4f1zNbXkd1435×157 15.5 KB

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;
}
#2

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. :slight_smile:

Try stress testing as suggested below: