Submission #70920

#	Time	Username	Problem	Language	Result	Execution time	Memory
70920		MANcity	Ideal city (IOI12_city)	C++14	55 / 100	218 ms	24540 KiB

city

#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
const LL maMod=1000*1000*1000;
int N;
int X[200002];
int Y[200002];
int dist[3002][3002];
int used[2002];
vector<vector<int> > g(3002);
void bfs(int v)
{
    int p_now=v;
    for0(i,N-1)
        used[i]=0;
    queue<int> myque;
    myque.push(v);
    while(!myque.empty())
    {
        int v=myque.front();
        for0(j,g[v].size()-1)
        {
            int to=g[v][j];
            if(used[to]==0)
            {
                dist[p_now][to]=dist[p_now][v]+1;
                used[to]=1;
                myque.push(to);
            }
        }
        myque.pop();
    }
}
pair<LL,int> Sx[100002];
pair<LL,int> Sy[100002];
int posx[100002];
int posy[100002];
pair<int,int> t[4*100002];
void update(int left,int right,int pos,int v,pair<int,int> val)
{
    if(left==right)
        t[v]=val;
    else
    {
        int m=(left+right)/2;
        if(pos<=m)
            update(left,m,pos,2*v,val);
        else
            update(m+1,right,pos,2*v+1,val);
        t[v].first=(t[2*v].first+t[2*v+1].first);
        t[v].second=(t[2*v].second+t[2*v+1].second);
    }
}
pair<int,int> get(int left,int right,int l,int r,int v)
{
    if(l>r)
        return {0,0};
    if(left==l && right==r)
        return t[v];
    int m=(left+right)/2;
    pair<int,int> A=get(left,m,l,min(r,m),2*v);
    pair<int,int> B=get(m+1,right,max(l,m+1),r,2*v+1);
    return {A.first+B.first,A.second+B.second};
}
int DistanceSum(int N_0, int *X_0, int *Y_0) {
    N=N_0;
    for0(i,N-1)
        X[i]=X_0[i];
    for0(i,N-1)
        Y[i]=Y_0[i];
    if(N<=2000)
    {
        for0(i,N-1)
            for0(j,N-1)
            {
                if(i!=j)
                {
                    int dist=abs(X[i]-X[j])+abs(Y[i]-Y[j]);
                    if(dist==1)
                    {
                        g[i].push_back(j);
                    }
                }
            }
        for0(i,N-1)
            bfs(i);
        LL sumdist=0;
        for0(i,N-1)
            fo(j,i+1,N-1)
                sumdist=(sumdist+dist[i][j])%Mod;
        /*cout<<sumdist<<endl;
        cout<<endl;
        cout<<endl;
        cout<<endl;*/
        return sumdist;
    }
    for0(i,N-1)
        Sx[i]={X[i],i};
    for0(i,N-1)
        Sy[i]={Y[i],i};
    sort(Sx,Sx+N);
    sort(Sy,Sy+N);
    for0(i,N-1)
        posx[Sx[i].second]=i;
    for0(i,N-1)
        posy[Sy[i].second]=i;
    update(0,N-1,posy[Sx[0].second],1,{1,Y[Sx[0].second]});
    LL SUM_X=Sx[0].first;
    LL SUM_DIST=0;
    for1(i,N-1)
    {
        SUM_DIST=(SUM_DIST+(LL)(i)*(LL)Sx[i].first)%maMod;
        SUM_DIST=(SUM_DIST-SUM_X+maMod+maMod)%maMod;
        int repos=Sx[i].second;
        int ypos=posy[repos];
        pair<int,int> SUM_POQR=get(0,N-1,0,ypos-1,1);
        pair<int,int> SUM_MEC=get(0,N-1,ypos+1,N-1,1);
        int qan_poqr=SUM_POQR.first;
        int qan_mec=SUM_MEC.first;
        SUM_DIST=(SUM_DIST+(LL)qan_poqr*(LL)Y[repos]);
        SUM_DIST=(SUM_DIST-SUM_POQR.second+maMod+maMod)%maMod;
        SUM_DIST=(SUM_DIST-(LL)qan_mec*(LL)Y[repos]+maMod+maMod)%maMod;
        SUM_DIST=(SUM_DIST+SUM_MEC.second)%maMod;
        SUM_X=(SUM_X+Sx[i].first)%maMod;
        update(0,N-1,ypos,1,{1,Y[repos]});
    }
    return (SUM_DIST+maMod)%maMod;
}
/*
5
1 1
1 2
2 2
2 3
3 3
*/

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