Submission #415543

#	Time	Username	Problem	Language	Result	Execution time	Memory
415543		snasibov05	Ideal city (IOI12_city)	C++14	23 / 100	30 ms	2716 KiB

city

#include <iostream>
#include <vector>

using namespace std;

#define oo 1000000000
#define ll long long
#define pb push_back

const ll m = 1e9;

vector<int> getCnt(int n, int k, int* x, int* y){
    vector<int> mn(k+1, oo), mx(k+1);
    for (int i = 0; i < n; ++i) {
        mn[x[i]] = min(mn[x[i]], y[i]);
        mx[x[i]] = max(mx[x[i]], y[i]);
    }

    vector<int> cnt(k+1);
    for (int i = 1; i <= k; ++i) {
        if (mx[i] == 0) continue;
        cnt[i] = mx[i] - mn[i] + 1;
    }

    return cnt;
}

int getDist(vector<int> v){
    int n = v.size();
    vector<ll> s(n+1), si(n+1);

    for (int i = n-1; i > 0; --i) {
        s[i] = (s[i+1] + v[i]) % m;
        si[i] = (si[i+1] + s[i]) % m;
    }

    int res = 0;
    for (int i = 1; i < n; ++i) {
        ll k = (v[i] * si[i+1]);
        res += (int)(k % m);
        res %= m;
    }

    return res;
}

int DistanceSum(int n, int *x, int *y) {

    int mn_x = oo, mn_y = oo;
    for (int i = 0; i < n; ++i) {
        mn_x = min(mn_x, x[i]);
        mn_y = min(mn_y, y[i]);
    }

    int mx_x = 0, mx_y = 0;

    for (int i = 0; i < n; ++i) {
        x[i] = x[i] - mn_x + 1;
        y[i] = y[i] - mn_y + 1;
        mx_x = max(x[i], mx_x);
        mx_y = max(y[i], mx_y);
    }

    vector<int> col = getCnt(n, mx_x, x, y);
    vector<int> row = getCnt(n, mx_y, y, x);

    int ans = getDist(col);
    ans += getDist(row);
    ans %= m;

    return ans;

}

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