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 GCC optimize ("O3")
#pragma GCC target ("avx2")
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>
using namespace std;
struct seg{
int id,l,r;
};
void dfs(int s, int p, vector<vector<int> > &adj, vector<int> &d){
for(auto u: adj[s]){
if(u==p) continue;
dfs(u,s,adj,d);
d[s]+=d[u];
}
}
long long solve(int N, int *X, int *Y){
long long int ans=0;
map<int, vector<int> >mapi;
for(int i=0; i<N; i++){
mapi[X[i]].push_back(Y[i]);
}
int c=0;
map<int, vector<seg> > comp;
for(auto &u: mapi){
sort(u.second.begin(), u.second.end());
int l=u.second[0],r=l;
for(int i=1; i<u.second.size(); i++){
if(u.second[i]==u.second[i-1]+1) r++;
else{
comp[u.first].push_back({c,l,r});
l=r=u.second[i];
c++;
}
}
comp[u.first].push_back({c,l,r});
c++;
}
vector<vector<int> > adj(c, vector<int>());
for(const auto &u: comp){
int y=u.first;
if(comp[y+1].size()==0){
comp.erase(y+1);
continue;
}
vector<seg> v1=comp[y];
vector<seg> v2=comp[y+1];
int i=0, j=0;
int n=v1.size(), m=v2.size();
while(i<n && j<m) {
int l=max(v1[i].l, v2[j].l);
int r=min(v1[i].r, v2[j].r);
if(l <= r){
adj[v1[i].id].push_back(v2[j].id);
adj[v2[j].id].push_back(v1[i].id);
}
if(v1[i].r<v2[j].r) i++;
else j++;
}
}
vector<int> subtreesize(c);
for(const auto &u: comp){
for(const seg i: u.second){
subtreesize[i.id]=i.r-i.l+1;
}
}
dfs(0, -1, adj, subtreesize);
for(int i=0; i<c; i++){
for(int j: adj[i]){
if(j>i){
int k=min(subtreesize[i], subtreesize[j]);
ans+=k*(N-k);
ans%=1'000'000'000;
}
}
}
return ans;
}
int DistanceSum(int N, int *X, int *Y) {
long long ans=0;
ans+=solve(N,X,Y);
ans+=solve(N,Y,X);
ans%=1000'000'000;
return ans;
}
Compilation message (stderr)
city.cpp: In function 'long long int solve(int, int*, int*)':
city.cpp:86:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i=1; i<u.second.size(); i++){
| ~^~~~~~~~~~~~~~~~
# | 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... |