| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 810863 | ma_moutahid | Ideal city (IOI12_city) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "cave.h"
using ll =long long;
#define int ll
ll LINF=1000000000000000000;
int INF=1000000000;
#define pi pair<int,int>
#define pl pair<ll,ll>
#define endl '\n'
#define vi vector<int>
#define vii vector<vector<int>>
#define vl vector<ll>
#define vll vector<vector<ll>>
//#define int ll
using namespace std;
int DistanceSum(int n,int *X,int *Y){
map<int,set<int>>x;
map<int,set<int>>y;
map<pi,pi>pos;
int mod=1e9;
for(int i=0;i<n;i++){
x[X[i]].insert(Y[i]);
y[Y[i]].insert(X[i]);
}
for(auto &itr:x){
int xpos=itr.first;
int p=0;
for(auto i=itr.second.begin();i!=itr.second.end();i++){
pos[make_pair(xpos,*i)].second=p;
p++;
}
}
for(auto &itr:y){
int ypos=itr.first;
int p=0;
for(auto i=itr.second.begin();i!=itr.second.end();i++){
pos[make_pair(*i,ypos)].first=p;
p++;
}
}
int result=0;
for (auto& itr:x){
int tbc=0;
int count=0;
int dist=0;
int xpos=itr.first;
for(auto p:itr.second){
int total=y[p].size();
int left=pos[make_pair(xpos,p)].second;
int right=total-1-left;
int temp=right*(right+1)/2 + left*(left+1)/2;
dist+= dist;
dist+=count;
dist+=temp;
tbc+=temp;
count+=total;
dist%=mod;
tbc%=mod;
}
result-=tbc;
result+=dist;
result+=mod;
result%=mod;
}
for (auto t=x.cbegin();t!=x.cend();t++){
auto &itr=*t;
int count=0;
int dist=0;
int xpos=itr.first;
int tbc=0;
for(auto p:itr.second){
int total=y[p].size();
int left=pos[make_pair(xpos,p)].second;
int right=total-1-left;
int temp=right*(right+1)/2 + left*(left+1)/2;
dist+= dist;
dist+=count;
dist+=temp;
tbc+=temp;
count+=total-1;
dist%=mod;
tbc%=mod;
}
result-=tbc;
result+=dist;
result+=mod;
result%=mod;
}
return result;
}