#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;
template<int mod>
struct modint{
int v;
modint(ll vv=0){s(vv%mod+mod);}
modint& s(int vv){
v=vv<mod?vv:vv-mod;
return *this;
}
modint operator-()const{return modint()-*this;}
modint& operator+=(const modint&rhs){return s(v+rhs.v);}
modint&operator-=(const modint&rhs){return s(v+mod-rhs.v);}
modint&operator*=(const modint&rhs){
v=ll(v)*rhs.v%mod;
return *this;
}
modint&operator/=(const modint&rhs){return *this*=rhs.inv();}
modint operator+(const modint&rhs)const{return modint(*this)+=rhs;}
modint operator-(const modint&rhs)const{return modint(*this)-=rhs;}
modint operator*(const modint&rhs)const{return modint(*this)*=rhs;}
modint operator/(const modint&rhs)const{return modint(*this)/=rhs;}
modint pow(int n)const{
modint res(1),x(*this);
while(n){
if(n&1)res*=x;
x*=x;
n>>=1;
}
return res;
}
modint inv()const{return pow(mod-2);}
/*modint inv()const{
int x,y;
int g=egcd(v,mod,x,y);
assert(g==1);
if(x<0)x+=mod;
return modint(x);
}*/
friend modint operator+(int x,const modint&y){return modint(x)+y;}
friend modint operator-(int x,const modint&y){return modint(x)-y;}
friend modint operator*(int x,const modint&y){return modint(x)*y;}
friend modint operator/(int x,const modint&y){return modint(x)/y;}
friend ostream& operator<<(ostream&os,const modint&m){return os<<m.v;}
friend istream& operator>>(istream&is,modint&m){
ll x;is>>x;
m=modint(x);
return is;
}
bool operator<(const modint&r)const{return v<r.v;}
bool operator==(const modint&r)const{return v==r.v;}
bool operator!=(const modint&r)const{return v!=r.v;}
explicit operator bool()const{return v;}
};
using mint=modint<mod>;
int n;
pii p[100010];
map<pii,int> mem;
vi g[100010];
int par[100010],xl[100010],xr[100010];
mint 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) {
mint ds=0,ss=0;
for(auto& it:g[u]) {
if(it==p)continue;
dfs(u,it,dep+1);
tot+=(dp[it]-dep*sub[it])*(xr[u]-xl[u]+1);
tot+=(ds-dep*ss)*sub[it]+(dp[it]-dep*sub[it])*ss;
ds+=dp[it];
ss+=sub[it];
}
dp[u]=ds+dep*(xr[u]-xl[u]+1);
sub[u]=ss+xr[u]-xl[u]+1;
}
mint 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];
mint ans=solve();
rep(i,n)swap(p[i].fi,p[i].se);
ans+=solve();
return ans.v;
}
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...);
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
3456 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
3456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
3584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
5880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
5880 KB |
Output is correct |
| 2 |
Correct |
81 ms |
5892 KB |
Output is correct |
| 3 |
Correct |
246 ms |
9336 KB |
Output is correct |
| 4 |
Incorrect |
233 ms |
9208 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
