This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma once
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <assert.h>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
/*
1 11 N <= 2e2 O(n^2)
2 21 N <= 2e3 O(n^2)
3 23 N <= 1e5
4 45 N <= 1e5
For 3 any two cell such x[i]<=x[j] then for all x such that x[i]<=x<=x[j] there is non empty cell there
*/
const int N=2001;
vector<int> ma[N];
bool vis[N];
int h[N];
int DistanceSum(int n, int x[], int y[])
{
if(n<=2000)
{
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if((abs(x[i]-x[j])+abs(y[i]-y[j]))==1)
{
ma[i].push_back(j);
ma[j].push_back(i);
}
}
}
long long ans1=0;
long long mod=1e9;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
h[j]=0;
vis[j]=0;
}
queue<int> q;
q.push(i);
vis[i]=1;
long long ans=0;
while(q.size())
{
int x=q.front();
ans+=(long long)h[x];
q.pop();
for(int y:ma[x])
{
if(!vis[y])
{
vis[y]=1;
h[y]=h[x]+1;
q.push(y);
}
}
}
ans1+=ans;
}
ans1/=2;
return ans1%mod;
}
long long other=0;
long long mod=1e9;
sort(x,x+n);
sort(y,y+n);
long long tot=0;
for(int i=0;i<n;i++)
tot+=x[i];
long long pr=0;
for(int i=0;i<n;i++)
{
pr+=x[i];
tot-=x[i];
other+=(((i+1)*x[i])-pr);
other+=(tot-((n-i-1)*x[i]));
}
long long sm=(other/2)%mod;
tot=0;
pr=0;
other=0;
for(int j=0;j<n;j++)
{
tot+=y[j];
}
for(int i=0;i<n;i++)
{
pr+=y[i];
tot-=y[i];
other+=(((i+1)*y[i])-pr);
other+=(tot-((n-i-1)*y[i]));
}
other/=2;
other%=mod;
return (other+sm)%mod;
}
Compilation message (stderr)
city.cpp:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |