Submission #424679

#	Time	Username	Problem	Language	Result	Execution time	Memory
424679		Charis02	Ideal city (IOI12_city)	C++14	0 / 100	116 ms	3132 KiB

city

#include<iostream>
#include<map>
#include<vector>
#include<set>
#include<algorithm>
#define pi pair < int,int >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define MAXN 100004

using namespace std;

int seg[4*MAXN][2];
int id[MAXN];
map < int,int > mapper;
int mod = 1000000000;

void update(int low,int high,int pos,int slow)
{
    if(low==slow&&low==high)
    {
        seg[pos][0]++;
        seg[pos][1]+=id[slow];
        return;
    }
    if(low>slow||high<slow)
        return;

    int mid = (low+high) / 2;

    update(low,mid,pos*2+1,slow);
    update(mid+1,high,pos*2+2,slow);

    rep(id,0,2)
        seg[pos][id] = (seg[pos*2+1][id] + seg[pos*2+2][id])%mod;

    return;
}

pi query(int low,int high,int pos,int slow,int shigh)
{
    if(low >= slow && high <= shigh)
        return mp(seg[pos][0],seg[pos][1]);
    if(low>shigh||high<slow)
        return mp(0,0);

    int mid = (low+high)/2;

    pi q1 = query(low,mid,pos*2+1,slow,shigh);
    pi q2 = query(mid+1,high,pos*2+2,slow,shigh);
    q1.first = (q1.first+q2.first)%mod;
    q1.second = (q1.second+q2.second)%mod;

    return q1;
}

int DistanceSum(int N, int *X, int *Y)
{
    vector < pi > points;
    set < int > ys;

    rep(i,0,N)
    {
        points.push_back(mp(X[i],Y[i]));
        ys.insert(Y[i]);
    }

    int cnt = 0;

    for(set < int >::iterator it = ys.begin();it != ys.end();it++)
    {
        id[cnt] = *it;
        mapper[*it] = cnt++;
    }

    sort(points.begin(),points.end());

    int ans = 0;
    int sum = 0;

    rep(i,0,N)
    {
        int x = points[i].first;
        int y = mapper[points[i].second];
        ans = (ans+x*i-sum)%mod;
        sum = (sum+x)%mod;


        //cout << "here " << x << " " << y << "   " << ans << "  ->  ";
        pi q = query(0,cnt,0,0,y);
        ans = (ans + q.first*id[y] - q.second)%mod;

        q = query(0,cnt,0,y,cnt);
        ans = (ans - q.first*id[y] + q.second)%mod;

        update(0,cnt,0,y);
      //  cout << "and here " << x << " " << y << "   " << ans << endl;
    }

    return ans;
}

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