oj.uz

Submission #594411

# Submission time Handle Problem Language Result Execution time Memory
594411 2022-07-12T12:11:06 Z keta_tsimakuridze Adriatic (CEOI13_adriatic) C++14
100 / 100
 362 ms 56588 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 = 25e4 + 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 169 ms 49304 KB Output is correct
2 Correct 177 ms 49376 KB Output is correct
3 Correct 173 ms 49380 KB Output is correct
4 Correct 205 ms 49312 KB Output is correct
5 Correct 175 ms 49372 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 49332 KB Output is correct
2 Correct 183 ms 49396 KB Output is correct
3 Correct 170 ms 49340 KB Output is correct
4 Correct 172 ms 49448 KB Output is correct
5 Correct 188 ms 49404 KB Output is correct
6 Correct 197 ms 49396 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 49372 KB Output is correct
2 Correct 179 ms 49440 KB Output is correct
3 Correct 218 ms 49380 KB Output is correct
4 Correct 202 ms 49436 KB Output is correct
5 Correct 190 ms 49460 KB Output is correct
6 Correct 191 ms 49372 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 49872 KB Output is correct
2 Correct 187 ms 49808 KB Output is correct
3 Correct 191 ms 49736 KB Output is correct
4 Correct 186 ms 49800 KB Output is correct
5 Correct 172 ms 49804 KB Output is correct
6 Correct 201 ms 49808 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 54532 KB Output is correct
2 Correct 265 ms 56288 KB Output is correct
3 Correct 253 ms 56236 KB Output is correct
4 Correct 258 ms 55864 KB Output is correct
5 Correct 261 ms 56440 KB Output is correct
6 Correct 362 ms 56412 KB Output is correct
7 Correct 304 ms 56588 KB Output is correct