oj.uz

Submission #70912

# Submission time Handle Problem Language Result Execution time Memory
70912 2018-08-23T16:42:51 Z MANcity Ideal city (IOI12_city) C++14
32 / 100
 207 ms 16636 KB 
#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[2002];
int Y[2002];
int dist[2002][2002];
int used[2002];
vector<vector<int> > g(2002);
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[1000002];
int posy[1000002];
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<=3000)
    {
        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;
        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-1)*(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.first+maMod+maMod)%maMod;
        SUM_DIST=(SUM_DIST-(LL)qan_mec*(LL)Y[repos]+maMod+maMod)%maMod;
        SUM_DIST=(SUM_DIST+SUM_MEC.first)%maMod;
        SUM_X=(SUM_X+Sx[i].first)%maMod;
        update(0,N-1,ypos,1,{1,Y[repos]});
    }
    return SUM_DIST%maMod;
}
/*11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 532 KB Output is correct
4 Correct 4 ms 964 KB Output is correct
5 Correct 3 ms 964 KB Output is correct
6 Correct 6 ms 1512 KB Output is correct
7 Correct 5 ms 1564 KB Output is correct
8 Correct 4 ms 1564 KB Output is correct
9 Correct 6 ms 1648 KB Output is correct
10 Correct 5 ms 1648 KB Output is correct
11 Correct 5 ms 1648 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 8600 KB Output is correct
2 Correct 48 ms 8600 KB Output is correct
3 Correct 110 ms 12456 KB Output is correct
4 Correct 125 ms 12468 KB Output is correct
5 Correct 182 ms 16524 KB Output is correct
6 Correct 199 ms 16588 KB Output is correct
7 Correct 177 ms 16588 KB Output is correct
8 Correct 207 ms 16588 KB Output is correct
9 Correct 201 ms 16636 KB Output is correct
10 Correct 181 ms 16636 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 16636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 16636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -