oj.uz

Submission #415543

# Submission time Handle Problem Language Result Execution time Memory
415543 2021-06-01T08:29:04 Z snasibov05 Ideal city (IOI12_city) C++14
23 / 100
 30 ms 2716 KB 
#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.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 204 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 5 ms 460 KB Output is correct
2 Correct 5 ms 588 KB Output is correct
3 Correct 13 ms 816 KB Output is correct
4 Correct 11 ms 876 KB Output is correct
5 Correct 23 ms 1196 KB Output is correct
6 Correct 22 ms 1772 KB Output is correct
7 Correct 30 ms 2104 KB Output is correct
8 Correct 23 ms 1860 KB Output is correct
9 Correct 22 ms 1920 KB Output is correct
10 Correct 22 ms 2716 KB Output is correct

Subtask #4
0 / 45.0

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