oj.uz

Submission #23452

# Submission time Handle Problem Language Result Execution time Memory
23452 2017-05-09T16:48:56 Z Bruteforceman Adriatic (CEOI13_adriatic) C++11
100 / 100
 499 ms 224580 KB 
#include <bits/stdc++.h>
using namespace std;
int cnt[2505][2505];
long long dp[2505][2505];
long long fn[2505][2505];

pair <int, int> top[2505][2505];
pair <int, int> bot[2505][2505];
pair <int, int> point[250005];

const int maxn = 2500;
const int inf = 1e8;


int get_sum(int _top, int _bottom, int _left, int _right) {
    if(_top > _bottom) return 0;
    if(_left > _right) return 0;
    return cnt[_bottom][_right] - cnt[_top - 1][_right] - cnt[_bottom][_left - 1] + cnt[_top - 1][_left - 1];
}

void nextDp(int i, int j) {
            int p = max(i, bot[i + 1][j + 1].first);
            int q = min(j, top[i - 1][j - 1].second);
            cout << p << " " << q << endl;
}
void nextFn(int i, int j) {
            int p = max(i, bot[i + 1][j + 1].first);
            int q = min(j, top[i - 1][j - 1].second);
            cout << p << " " << q << endl;
}

int main() {

    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        point[i] = make_pair(x, y);

        cnt[x][y] += 1;
    }
    for(int i = 1; i <= maxn; i++) {
        for(int j = 1; j <= maxn; j++) {
            cnt[i][j] += cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1];
        }
    }

    for(int i = 1; i <= maxn; i++) {
        for(int j = 1; j <= maxn; j++) {
            if(get_sum(i, i, 1, j)) top[i][j].first = i;
            else top[i][j].first = inf;
            if(i > 1) top[i][j].first = min(top[i][j].first, top[i-1][j].first);

            if(get_sum(1, i, j, j)) top[i][j].second = j;
            else top[i][j].second = inf;
            if(j > 1) top[i][j].second = min(top[i][j].second, top[i][j-1].second);
        }
    }
    for(int i = maxn; i >= 1; i--) {
        for(int j = maxn; j >= 1; j--) {
            if(get_sum(i, i, j, maxn)) bot[i][j].first = i;
            else bot[i][j].first = 0;
            if(i < maxn) bot[i][j].first = max(bot[i][j].first, bot[i + 1][j].first);

            if(get_sum(i, maxn, j, j)) bot[i][j].second = j;
            else bot[i][j].second = 0;
            if(j < maxn) bot[i][j].second = max(bot[i][j].second, bot[i][j + 1].second);
        }
    }
    for(int i = 0; i <= maxn; i++) {
        top[0][i] = make_pair(inf, inf);
        top[i][0] = make_pair(inf, inf);
    }
    for(int i = 0; i <= maxn; i++) {
        bot[maxn + 1][i] = make_pair(0, 0);
        bot[i][maxn + 1] = make_pair(0, 0);
    }
    for(int i = 1; i <= maxn; i++) {
        for(int j = maxn; j >= 1; j--) {
            int p = min(i, top[i - 1][j - 1].first);
            int q = max(j, bot[i + 1][j + 1].second);
            if(p == i && q == j) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = dp[p][q] + get_sum(1, i, j, maxn);
            }
        }
    }
    for(int i = maxn; i >= 1; i--) {
        for(int j = 1; j <= maxn; j++) {
            int p = max(i, bot[i + 1][j + 1].first);
            int q = min(j, top[i - 1][j - 1].second);

            if(p == i && q == j) {
                fn[i][j] = 0;
            } else {
                fn[i][j] = fn[p][q] + get_sum(i, maxn, 1, j);
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        int x = point[i].first;
        int y = point[i].second;
        long long ans = get_sum(1, x-1, 1, y-1) + get_sum(x+1, maxn, y+1, maxn);
        ans += max(0LL, dp[x][y] - 1);
        ans += max(0LL, fn[x][y] - 1);
        ans += get_sum(x, maxn, 1, y) - 1;
        ans += get_sum(1, x, y, maxn) - 1;

        // cout << fn[x][y] << " " << dp[x][y] << endl;
        printf("%lld\n", ans);
    }
    return 0;
}

Compilation message

adriatic.cpp: In function 'int main()':
adriatic.cpp:35:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
adriatic.cpp:38:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y);
                               ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 224580 KB Output is correct
2 Correct 246 ms 224580 KB Output is correct
3 Correct 223 ms 224580 KB Output is correct
4 Correct 253 ms 224580 KB Output is correct
5 Correct 296 ms 224580 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 224580 KB Output is correct
2 Correct 299 ms 224580 KB Output is correct
3 Correct 296 ms 224580 KB Output is correct
4 Correct 273 ms 224580 KB Output is correct
5 Correct 259 ms 224580 KB Output is correct
6 Correct 319 ms 224580 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 224580 KB Output is correct
2 Correct 323 ms 224580 KB Output is correct
3 Correct 283 ms 224580 KB Output is correct
4 Correct 259 ms 224580 KB Output is correct
5 Correct 303 ms 224580 KB Output is correct
6 Correct 356 ms 224580 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 224580 KB Output is correct
2 Correct 283 ms 224580 KB Output is correct
3 Correct 296 ms 224580 KB Output is correct
4 Correct 273 ms 224580 KB Output is correct
5 Correct 289 ms 224580 KB Output is correct
6 Correct 376 ms 224580 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 224580 KB Output is correct
2 Correct 486 ms 224580 KB Output is correct
3 Correct 493 ms 224580 KB Output is correct
4 Correct 499 ms 224580 KB Output is correct
5 Correct 423 ms 224580 KB Output is correct
6 Correct 433 ms 224580 KB Output is correct
7 Correct 469 ms 224580 KB Output is correct