제출 #415541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415541		snasibov05	Ideal city (IOI12_city)	C++14	0 / 100	21 ms	1064 KiB

city

#include <iostream>
#include <vector>

using namespace std;

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

const int 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<int> s(n+1), si(n+1);

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

    int res = 0;
    for (int i = 1; i < n; ++i) {
        res += (v[i] * si[i+1]) * 1ll % 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: 0 / 23
• Subtask 4: 0 / 45