Submission #812311

#	Time	Username	Problem	Language	Result	Execution time	Memory
812311		ma_moutahid	Ideal city (IOI12_city)	C++17	0 / 100	23 ms	4084 KiB

city

#include <bits/stdc++.h>
using ll =long long;
//#define int ll
ll LINF=1000000000000000000;
int INF=1000000000;
#define pi pair<int,int>
#define pl pair<ll,ll>
#define endl '\n'
#define vi vector<int>
#define vii vector<vector<int>>
#define vl vector<ll>
#define vll vector<vector<ll>>
using namespace std;



int DistanceSum(int n,int *X,int *Y){
    map<ll,set<ll>>x;
    map<ll,set<ll>>y;
    map<pl,pl>pos;
    ll mod=1e9;
    for(ll i=0;i<n;i++){
        x[X[i]].insert(Y[i]);
        y[Y[i]].insert(X[i]);
    }
    for(auto &itr:x){
        ll xpos=itr.first;
        ll p=0;
        for(auto i=itr.second.begin();i!=itr.second.end();i++){
            pos[make_pair(xpos,*i)].second=p;
            p++;
        }
    }
    for(auto &itr:y){
        int ypos=itr.first;
        int p=0;
        for(auto i=itr.second.begin();i!=itr.second.end();i++){
            pos[make_pair(*i,ypos)].first=p;
            p++;
        }
    }

    ll result=0;
    for (auto& itr:x){
        ll tbc=0;
        ll count=0;
        ll dist=0;
        ll xpos=itr.first;
        for(auto p:itr.second){
            ll total=y[p].size();
            ll left=pos[make_pair(xpos,p)].second;
            ll right=total-1-left;
            ll temp=right*(right+1)/2 + left*(left+1)/2;
            dist+= dist;
            dist+=count;
            dist+=temp;
            tbc+=temp;
            count+=total;
            dist%=mod;
            tbc%=mod;
        }
        result-=tbc;
        result+=dist;
        result+=mod;
        result%=mod;


    }
    for (auto t=x.cbegin();t!=x.cend();t++){
        auto &itr=*t;
        ll count=0;
        ll dist=0;
        ll xpos=itr.first;
        ll tbc=0;
        for(auto p:itr.second){
            ll total=y[p].size();
            ll left=pos[make_pair(xpos,p)].second;
            ll right=total-1-left;
            ll temp=right*(right+1)/2 + left*(left+1)/2;
            dist+= dist;
            dist+=count;
            dist+=temp;
            tbc+=temp;
            count+=total-1;
            dist%=mod;
            tbc%=mod;
        }
        result-=tbc;
        result+=dist;
        result+=mod;
        result%=mod;
    }
    return result;

}

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