oj.uz

Submission #53243

# Submission time Handle Problem Language Result Execution time Memory
53243 2018-06-29T05:23:45 Z 강태규(#1399) Adriatic (CEOI13_adriatic) C++11
100 / 100
 282 ms 91620 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const int W = 2500;
int n;
int x[250000], y[250000];
int sum[2501][2501];
int lu[2501];
int dr[2502];
int ul[2501];
int rd[2502];
int ans1[2501][2501];
int ans2[2501][2501];

int getSum(int x1, int y1, int x2, int y2) {
    return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}

int main() {
    for (int i = 0; i <= W; ++i) {
        lu[i] = ul[i] = W + 1;
    }
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", x + i, y + i);
        sum[x[i]][y[i]] = 1;
        lu[x[i]] = min(lu[x[i]], y[i]);
        rd[x[i]] = max(rd[x[i]], y[i]);
        ul[y[i]] = min(ul[y[i]], x[i]);
        dr[y[i]] = max(dr[y[i]], x[i]);
    }
    
    for (int i = 1; i <= W; ++i) {
        for (int j = 1; j <= W; ++j) {
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
    
    for (int i = 1; i <= W; ++i) {
        lu[i] = min(lu[i], lu[i - 1]);
        ul[i] = min(ul[i], ul[i - 1]);
    }
    
    for (int i = W; i; --i) {
        rd[i] = max(rd[i], rd[i + 1]);
        dr[i] = max(dr[i], dr[i + 1]);
    }
    for (int i = W; i; --i) {
        for (int j = 1; j <= W; ++j) {
            int l = min(lu[i - 1], j);
            int d = max(dr[j + 1], i);
            ans1[i][j] = ans1[d][l] + getSum(i, 1, W, j);
        }
    }
    for (int i = 1; i <= W; ++i) {
        for (int j = W; j; --j) {
            int l = min(ul[j - 1], i);
            int d = max(rd[i + 1], j);
            ans2[i][j] = ans2[l][d] + getSum(1, j, i, W);
        }
    }
    for (int i = 0; i < n; ++i) {
        printf("%d\n", ans1[x[i]][y[i]] + ans2[x[i]][y[i]] + n - 3);
    }
	return 0;
}

Compilation message

adriatic.cpp: In function 'int main()':
adriatic.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
adriatic.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", x + i, y + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 73720 KB Output is correct
2 Correct 106 ms 73800 KB Output is correct
3 Correct 103 ms 73904 KB Output is correct
4 Correct 107 ms 73920 KB Output is correct
5 Correct 103 ms 73952 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 74084 KB Output is correct
2 Correct 111 ms 74084 KB Output is correct
3 Correct 110 ms 74084 KB Output is correct
4 Correct 109 ms 74128 KB Output is correct
5 Correct 105 ms 74128 KB Output is correct
6 Correct 115 ms 74128 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 74128 KB Output is correct
2 Correct 122 ms 74128 KB Output is correct
3 Correct 112 ms 74192 KB Output is correct
4 Correct 106 ms 74192 KB Output is correct
5 Correct 109 ms 74192 KB Output is correct
6 Correct 129 ms 74324 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 74532 KB Output is correct
2 Correct 120 ms 74532 KB Output is correct
3 Correct 125 ms 74532 KB Output is correct
4 Correct 119 ms 74532 KB Output is correct
5 Correct 109 ms 74532 KB Output is correct
6 Correct 130 ms 74576 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 77988 KB Output is correct
2 Correct 261 ms 80044 KB Output is correct
3 Correct 257 ms 82272 KB Output is correct
4 Correct 231 ms 84160 KB Output is correct
5 Correct 237 ms 86812 KB Output is correct
6 Correct 282 ms 89052 KB Output is correct
7 Correct 271 ms 91620 KB Output is correct