oj.uz

Submission #810898

# Submission time Handle Problem Language Result Execution time Memory
810898 2023-08-06T17:15:35 Z ma_moutahid Ideal city (IOI12_city) C++17
0 / 100
 22 ms 3668 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<int,set<int>>x;
    map<int,set<int>>y;
    map<pi,pi>pos;
    int mod=1e9;
    for(int i=0;i<n;i++){
        x[X[i]].insert(Y[i]);
        y[Y[i]].insert(X[i]);
    }
    for(auto &itr:x){
        int xpos=itr.first;
        int 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++;
        }
    }

    int result=0;
    for (auto& itr:x){
        int tbc=0;
        int count=0;
        int dist=0;
        int xpos=itr.first;
        for(auto p:itr.second){
            int total=y[p].size();
            int left=pos[make_pair(xpos,p)].second;
            int right=total-1-left;
            int 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;
        int count=0;
        int dist=0;
        int xpos=itr.first;
        int tbc=0;
        for(auto p:itr.second){
            int total=y[p].size();
            int left=pos[make_pair(xpos,p)].second;
            int right=total-1-left;
            int 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 0 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 468 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 3636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

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