Submission #413130

#	Time	Username	Problem	Language	Result	Execution time	Memory
413130		A_D	Ideal city (IOI12_city)	C++14	0 / 100	12 ms	1512 KiB

city

#include <bits/stdc++.h>

#define LL long long

using namespace std;
const int MOD=1e9;
vector<LL> x,y;
vector<LL> prex,prey;
int DistanceSum(int N,int *X,int *Y){
    x.clear();prex.clear();y.clear();prey.clear();

    for(int i=0;i<N;i++){
        x.push_back(X[i]);
        y.push_back(Y[i]);
    }
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    prex.push_back(x[0]);
    prey.push_back(y[0]);
    for(int i=1;i<N;i++){
        prex.push_back(prex[i-1]+x[i]);
        prey.push_back(prey[i-1]+y[i]);
    }
    LL ans=0;
    for(int i=0;i<N;i++){
         int l=0,r=N-1,ann;
         while(l<=r){
            int mid=(l+r)/2;
            if(x[mid]<=X[i]){
                ann=mid;
                l=mid+1;
            }
            else r=mid-1;
         }
         ans+=X[i]*(ann+1)-prex[ann];
         ans+=prex[N-1]-prex[ann]-(N-1-ann)*X[i];



         l=0,r=N-1;
         while(l<=r){
            int mid=(l+r)/2;
            if(y[mid]<=Y[i]){
                ann=mid;
                l=mid+1;
            }
            else r=mid-1;
         }
         ans+=Y[i]*(ann+1)-prey[ann];
         ans+=prey[N-1]-prey[ann]-(N-1-ann)*Y[i];
         ans%=MOD;
    }
    return ans/2;
}

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:37:39: warning: 'ann' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |          ans+=prex[N-1]-prex[ann]-(N-1-ann)*X[i];
      |                                   ~~~~^~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45