| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1215325 | segfault_ikuyo | 이상적인 도시 (IOI12_city) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
const int maxn=1e5+5;
const int mod=1e9;
int n,ans;
pii pt[maxn];
vector<int> adj[maxn];
int l[maxn],r[maxn],pos[maxn],cnt[maxn];
int siz[maxn];
bool cmp(pii a,pii b){
return (a.f==b.f)?(a.s<b.s):(a.f<b.f);
}
void dfs(int x,int p){
siz[x]=cnt[x];
for(int i:adj[x]){
if(i==p) continue;
dfs(i,x);
siz[x]+=siz[i];
}
ans+=(n-siz[x])*siz[x];
ans%=mod;
}
void solve(){
int idx=0;
l[0]=r[0]=pt[0].s;
pos[0]=pt[0].f;
cnt[0]=1;
for(int i=1;i<n;i++){
if(pt[i].f==pt[i-1].f&&pt[i].s==pt[i-1].s+1) {
r[idx]++;
cnt[idx]++;
}else{
pos[++idx]=pt[i].f;
l[idx]=r[idx]=pt[i].s;
cnt[idx]=1;
}
}
int low=0,high=0;
while(high<=idx){
if(pos[low]==pos[high]){
high++;
continue;
}
if(pos[low]!=pos[high]-1){
low++;
continue;
}
if(l[low]<=r[high]&&l[high]<=r[low]){
adj[low].pb(high);
adj[high].pb(low);
if(pos[high+1]!=pos[high]) low++;
else if(l[low]<=r[high+1]&&l[high+1]<=r[low]) high++;
else low++;
}else{
if(r[low]<l[high]) low++;
else if(r[high]<l[low]) high++;
}
}
dfs(0,-1);
}
signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n;
for(int i=0;i<n;i++) cin>>pt[i].f>>pt[i].s;
sort(pt,pt+n,cmp);
solve();
for(int i=0;i<n;i++) swap(pt[i].f,pt[i].s);
for(int i=0;i<n;i++) adj[i].clear();
sort(pt,pt+n,cmp);
solve();
cout<<ans;
}