oj.uz

Submission #812311

# Submission time Handle Problem Language Result Execution time Memory
812311 2023-08-07T08:20:46 Z ma_moutahid Ideal city (IOI12_city) C++17
0 / 100
 23 ms 4084 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 4052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 4084 KB Output isn't correct
2 Halted 0 ms 0 KB -