Submission #1317609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317609		miniob	Adriatic (CEOI13_adriatic)	C++20	100 / 100	460 ms	200584 KiB

adriatic

#include <bits/stdc++.h>
using namespace std;

int x[250007];
int y[250007];
int ile1[2507][2507];
int dp1[2507][2507];
int maxx1[2507][2507];
int maxy1[2507][2507];
int ile2[2507][2507];
int maxx2[2507][2507];
int maxy2[2507][2507];
int dp2[2507][2507];

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i <= 2501; i++)
    {
    	for(int j = 0; j <= 2501; j++)
    	{
    		maxy1[i][j] = INT_MAX;
    		maxx2[i][j] = INT_MAX;
    	}
    }
    for(int i = 0; i < n; i++)
    {
    	cin >> x[i] >> y[i];
    	ile1[x[i]][y[i]]++;
    	ile2[x[i]][y[i]]++;
    	maxx1[x[i]][y[i]] = y[i];
    	maxy1[x[i]][y[i]] = x[i];
        maxx2[x[i]][y[i]] = y[i];
    	maxy2[x[i]][y[i]] = x[i];
    }
    for(int i = 1; i <= 2500; i++)
    {
    	for(int j = 2500; j >= 1; j--)
    	{
    		ile1[i][j] += ile1[i][j + 1] + ile1[i - 1][j] - ile1[i - 1][j + 1];
    	}
    }
    for(int i = 2500; i >= 1; i--)
    {
    	for(int j = 2500; j >= 0; j--)
    	{
    		maxx1[i][j] = max(maxx1[i][j], max(maxx1[i + 1][j], maxx1[i][j + 1]));
    	}
    }
    for(int i = 1; i <= 2500; i++)
    {
    	for(int j = 1; j <= 2500; j++)
    	{
    		maxy1[i][j] = min(maxy1[i][j], min(maxy1[i - 1][j], maxy1[i][j - 1]));
    	}
    }
    for(int i = 1; i <= 2500; i++)
    {
    	for(int j = 2500; j > 0; j--)
    	{
    		dp1[i][j] = ile1[i][j] + dp1[min(i, maxy1[i - 1][j - 1])][max(j, maxx1[i + 1][j + 1])];
    	}
    }
    for(int i = 2500; i >= 1; i--)
    {
    	for(int j = 1; j <= 2500; j++)
    	{
    		ile2[i][j] += ile2[i][j - 1] + ile2[i + 1][j] - ile2[i + 1][j - 1];
    	}
    }
    for(int i = 2500; i >= 1; i--)
    {
    	for(int j = 2500; j >= 0; j--)
    	{
    		maxy2[i][j] = max(maxy2[i][j], max(maxy2[i + 1][j], maxy2[i][j + 1]));
    	}
    }
    for(int i = 1; i <= 2500; i++)
    {
    	for(int j = 1; j <= 2500; j++)
    	{
    		maxx2[i][j] = min(maxx2[i][j], min(maxx2[i - 1][j], maxx2[i][j - 1]));
    	}
    }
    for(int i = 2500; i >= 1; i--)
    {
    	for(int j = 1; j <= 2500; j++)
    	{
    		dp2[i][j] = ile2[i][j] + dp2[max(i,maxy2[i + 1][j + 1])][min(j, maxx2[i - 1][j - 1])];
    	}
    }
    for(int i = 0; i < n; i++)
    {
        cout << dp1[x[i]][y[i]] + dp2[x[i]][y[i]] + n - 3 << endl;
    }
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20