Submission #442810

#	Time	Username	Problem	Language	Result	Execution time	Memory
442810		prvocislo	Adriatic (CEOI13_adriatic)	C++17	100 / 100	237 ms	104396 KiB

adriatic

#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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20