oj.uz

Submission #424687

# Submission time Handle Problem Language Result Execution time Memory
424687 2021-06-12T09:09:08 Z Charis02 Ideal city (IOI12_city) C++14
23 / 100
 100 ms 3560 KB 
#include<iostream>
#include<map>
#include<vector>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#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;

ll seg[4*MAXN][2];
ll 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]=(seg[pos][1]+id[slow])%mod;
        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());

    ll ans = 0;
    ll sum = 0;

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

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

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

        update(0,cnt,0,y);
    }

    return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 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 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1224 KB Output is correct
2 Correct 12 ms 1224 KB Output is correct
3 Correct 42 ms 1988 KB Output is correct
4 Correct 32 ms 1988 KB Output is correct
5 Correct 88 ms 3388 KB Output is correct
6 Correct 68 ms 3560 KB Output is correct
7 Correct 100 ms 3420 KB Output is correct
8 Correct 94 ms 3488 KB Output is correct
9 Correct 60 ms 3452 KB Output is correct
10 Correct 44 ms 3444 KB Output is correct

Subtask #4
0 / 45.0

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