oj.uz

Submission #442810

# Submission time Handle Problem Language Result Execution time Memory
442810 2021-07-09T07:40:34 Z prvocislo Adriatic (CEOI13_adriatic) C++17
100 / 100
 237 ms 104396 KB 
#include <bits/stdc++.h>
using namespace std;

const int k = 2505;
int pf[k][k], r[k], u[k], l[k], d[k];
int dpru[k][k], dpld[k][k], a[k][k];
int sum(int r1, int c1, int r2, int c2)
{
    return pf[r2+1][c2+1] - pf[r2+1][c1] - pf[r1][c2+1] + pf[r1][c1];
}
void print(int x[k][k])
{
    cout << "================\n";
    for (int i = 1; i < k; i++) for (int j = 1; j < k; j++) cout << x[i][j] << " \n"[j==k-1];
    cout << "================\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); 
    for (int i = 0; i < k; i++) l[i] = u[i] = k, r[i] = d[i] = -1; 
    int n;
    cin >> n;
    vector<int> vx(n), vy(n);
    for (int i = 0; i < n; i++)
    {
        cin >> vx[i] >> vy[i];
        a[vx[i]][vy[i]] = 1;
        r[vx[i]] = max(r[vx[i]], vy[i]);
        l[vx[i]] = min(l[vx[i]], vy[i]);
        d[vy[i]] = max(d[vy[i]], vx[i]);
        u[vy[i]] = min(u[vy[i]], vx[i]);
    }
    for (int i = 1; i < k; i++) for (int j = 1; j < k; j++) pf[i][j] = pf[i-1][j] + pf[i][j-1] - pf[i-1][j-1] + a[i-1][j-1];
    //print(pf);
    for (int i = 1; i < k; i++)    l[i] = min(l[i], l[i-1]), u[i] = min(u[i], u[i-1]);
    for (int i = k-2; i >= 0; i--) r[i] = max(r[i], r[i+1]), d[i] = max(d[i], d[i+1]);
    for (int x = 1; x < k-2; x++) for (int y = k-3; y >= 1; y--)
    {
        int val = sum(0, y, x, k-2); 
        if (!val) continue;
        dpru[x][y] = val + dpru[min(x, u[y-1])][max(y, r[x+1])];
    }
    //print(dpru);
    for (int x = k-3; x >= 1; x--) for (int y = 1; y < k-2; y++)
    {
        int val = sum(x, 0, k-2, y); 
        if (!val) continue;
        dpld[x][y] = val + dpld[max(x, d[y+1])][min(y, l[x-1])];
    }
    //print(dpld);
    for (int i = 0; i < n; i++)
    {
        int suma = n + dpru[vx[i]][vy[i]] + dpld[vx[i]][vy[i]] - 3;
        cout << suma << "\n";
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 73796 KB Output is correct
2 Correct 96 ms 74068 KB Output is correct
3 Correct 93 ms 74040 KB Output is correct
4 Correct 65 ms 35652 KB Output is correct
5 Correct 94 ms 73652 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 78412 KB Output is correct
2 Correct 96 ms 79240 KB Output is correct
3 Correct 98 ms 78560 KB Output is correct
4 Correct 66 ms 37412 KB Output is correct
5 Correct 95 ms 73156 KB Output is correct
6 Correct 102 ms 76612 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 82420 KB Output is correct
2 Correct 99 ms 87664 KB Output is correct
3 Correct 105 ms 82936 KB Output is correct
4 Correct 72 ms 42452 KB Output is correct
5 Correct 96 ms 75220 KB Output is correct
6 Correct 143 ms 84044 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 85076 KB Output is correct
2 Correct 116 ms 98640 KB Output is correct
3 Correct 115 ms 85296 KB Output is correct
4 Correct 81 ms 48260 KB Output is correct
5 Correct 100 ms 76484 KB Output is correct
6 Correct 149 ms 84952 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 91068 KB Output is correct
2 Correct 237 ms 104396 KB Output is correct
3 Correct 232 ms 98876 KB Output is correct
4 Correct 177 ms 68036 KB Output is correct
5 Correct 183 ms 83948 KB Output is correct
6 Correct 219 ms 92612 KB Output is correct
7 Correct 221 ms 92184 KB Output is correct