Submission #1215327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215327		segfault_ikuyo	Ideal city (IOI12_city)	C++20	100 / 100	35 ms	9284 KiB

city

#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 DistanceSum(signed N,signed *X,signed *Y){
    n=N;
    for(int i=0;i<n;i++){
        pt[i].f=X[i];
        pt[i].s=Y[i];
    }
    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();
    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45