#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define mset(x,y) memset(x,y,sizeof(x))
#define rep(i,n) for(int i=0;i<int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
#ifdef LOCAL
#define dmp(...) _dmp(#__VA_ARGS__, __VA_ARGS__)
#else
#define dmp(...) (__VA_ARGS__)
#endif
template<class T> using vt=vector<T>;
template<class T> using vvt=vt<vt<T>>;
template<class TA,class TB> void chmax(TA&a,TB b){if(a<b)a=b;}
template<class TA,class TB> void chmin(TA&a,TB b){if(b<a)a=b;}
template<class TA,class TB>
ostream& operator<<(ostream& os,const pair<TA,TB>& p){
return os<<"{"<<p.fi<<","<<p.se<<"}";
}
template<class T> ostream& operator<<(ostream& os,const vt<T>& v){
os<<"{";for(auto& e:v)os<<e<<",";return os<<"}";
}
template<class TH> void _dmp(const char *sdbg, TH h){cout<<sdbg<<"="<<h<<endl;}
template<class TH, class... TA> void _dmp(const char *sdbg, TH h, TA...a){
while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
}
template<class T> void make_unique(vt<T>& v) {
sort(all(v));v.erase(unique(all(v)),v.end());
}
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
int ri(){int x;cin>>x;return x;}
ll rll(){ll x;cin>>x;return x;}
vi rvi(int n){vi v;rep(i,n)v.pb(ri());return v;}
const int mod=1e9;
int n;
pii p[100010];
map<pii,int> mem;
vi g[100010];
int par[100010],xl[100010],xr[100010];
int dp[100010],sub[100010],tot;
int pn(int u){return u==par[u]?u:(par[u]=pn(par[u]));}
void us(int a,int b){
a=pn(a),b=pn(b);
par[b]=a;
xl[a]=min(xl[a],xl[b]);
xr[a]=max(xr[a],xr[b]);
}
void dfs(int p,int u,int dep) {
int ds=0,ss=0;
for(auto& it:g[u]) {
if(it==p)continue;
dfs(u,it,dep+1);
tot+=(ll)(dp[it]-(ll)dep*sub[it]%mod+mod)%mod*(xr[u]-xl[u]+1)%mod;
tot%=mod;
tot+=((ds-(ll)dep*ss%mod+mod)%mod*sub[it]%mod+(dp[it]-(ll)dep*sub[it]%mod+mod)%mod*ss%mod)%mod;
tot%=mod;
ds+=dp[it];ds%=mod;
ss+=sub[it];
}
dp[u]=(ds+(ll)dep*(xr[u]-xl[u]+1)%mod)%mod;
sub[u]=ss+xr[u]-xl[u]+1;
}
int solve() {
tot=0;
mem.clear();
rep(i,n){
par[i]=i;
xl[i]=xr[i]=p[i].fi;
g[i].clear();
mem[p[i]]=i;
}
rep(i,n) {
if(mem.count(mp(p[i].fi-1,p[i].se)))
us(i,mem[mp(p[i].fi-1,p[i].se)]);
if(mem.count(mp(p[i].fi+1,p[i].se)))
us(i,mem[mp(p[i].fi+1,p[i].se)]);
}
rep(i,n) {
if(mem.count(mp(p[i].fi,p[i].se-1)))
g[pn(i)].pb(pn(mem[mp(p[i].fi,p[i].se-1)]));
if(mem.count(mp(p[i].fi,p[i].se+1)))
g[pn(i)].pb(pn(mem[mp(p[i].fi,p[i].se+1)]));
}
rep(i,n)if(par[i]==i)make_unique(g[i]);
dfs(0,0,0);
return tot;
}
int DistanceSum(int N, int *X, int *Y) {
n=N;
rep(i,n)p[i].se=Y[i],p[i].fi=X[i];
int ans=solve();
rep(i,n)swap(p[i].fi,p[i].se);
ans+=solve();ans%=mod;
return ans;
}
Compilation message
city.cpp: In function 'void _dmp(const char*, TH, TA ...)':
city.cpp:36:1: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
^~~~~
city.cpp:36:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
2688 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
2688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
2816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
78 ms |
5368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
80 ms |
5444 KB |
Output is correct |
| 2 |
Correct |
82 ms |
5368 KB |
Output is correct |
| 3 |
Correct |
227 ms |
9380 KB |
Output is correct |
| 4 |
Incorrect |
233 ms |
8696 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
