oj.uz

Submission #594408

# Submission time Handle Problem Language Result Execution time Memory
594408 2022-07-12T12:10:35 Z keta_tsimakuridze Adriatic (CEOI13_adriatic) C++14
80 / 100
 216 ms 50092 KB 
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair<int,int>
#define ll long long
const int N = 2e5 + 5, mod = 1e9 + 7, X = 2500;
int t, x[N], y[N], r[N], up[N];
int f[X + 5][X + 5];
int dp[X + 5][X + 5];
main() {
/*
7
1 7
7 5
4 5
4 8
6 6
6 1
2 3

4
1 1
2 3
3 2
4 4
*/
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
    vector<int> ans(n + 5);
    for(int t = 0; t < 2; t++) {
        for(int i = 1; i <= X; i++ ){
            for(int j = 1; j <= X; j++) f[i][j] = 0;
        }
        for(int i = 1; i <= n; i++) f[x[i]][y[i]] = 1;
        for(int i = X; i >= 1; i--) {
            r[i] = 0;
            for(int j = 1; j <= X; j++) {
                if(f[i][j]) r[i] = j;
            }
            r[i] = max(r[i], r[i + 1]);
        }
        up[0] = X + 1;
        for(int j = 1; j <= X; j++) {
            up[j] = X + 1;
            for(int i = 1; i <= X; i++) {
                if(f[i][j]) up[j] = min(up[j], i);
            }
            up[j] = min(up[j], up[j - 1]);
        }

        for(int i = 1; i <= X; i++) {
            for(int j = X; j >= 1; j--) {
                f[i][j] = f[i][j] + f[i][j + 1] + f[i - 1][j] - f[i - 1][j + 1];
                dp[i][j] = f[i][j] + dp[min(i, up[j - 1])][max(j, r[i + 1])];
            }
        }
        for(int i = 1; i <= n; i++) {
            ans[i] += dp[x[i]][y[i]] - 1;
           x[i] = X - x[i] + 1; y[i] = X - y[i] + 1;
        }

    }
    for(int i = 1; i <= n; i++) cout << ans[i] - 1 + n << "\n";
}

Compilation message

adriatic.cpp:11:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main() {
      | ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 49328 KB Output is correct
2 Correct 165 ms 49320 KB Output is correct
3 Correct 199 ms 49324 KB Output is correct
4 Correct 170 ms 49384 KB Output is correct
5 Correct 161 ms 49360 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 49344 KB Output is correct
2 Correct 185 ms 49352 KB Output is correct
3 Correct 190 ms 49416 KB Output is correct
4 Correct 162 ms 49408 KB Output is correct
5 Correct 164 ms 49348 KB Output is correct
6 Correct 194 ms 49356 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 49488 KB Output is correct
2 Correct 171 ms 49468 KB Output is correct
3 Correct 173 ms 49496 KB Output is correct
4 Correct 165 ms 49416 KB Output is correct
5 Correct 165 ms 49492 KB Output is correct
6 Correct 216 ms 49564 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 50016 KB Output is correct
2 Correct 170 ms 50024 KB Output is correct
3 Correct 188 ms 50092 KB Output is correct
4 Correct 170 ms 49988 KB Output is correct
5 Correct 165 ms 49984 KB Output is correct
6 Correct 180 ms 50016 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 5532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -