Submission #362890

#	Time	Username	Problem	Language	Result	Execution time	Memory
362890		GioChkhaidze	섬 항해 (CEOI13_adriatic)	C++14	100 / 100	308 ms	114668 KiB

adriatic

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 250005;
const int M = 2505;

int n, x[N], y[N];

int S[M][M], S_[M][M];
int dp[M][M], dp_[M][M];
int MaxX[M], MinX[M], MaxY[M], MinY[M];
vector < int > sx[M], sy[M];
bool f[M][M];

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> x[i] >> y[i];
		f[x[i]][y[i]] = true;
		sx[x[i]].push_back(y[i]);
		sy[y[i]].push_back(x[i]);
	}
	
	int U = 2500;
	for (int i = 1; i <= U; ++i) {
		sort(sx[i].begin(), sx[i].end());
		sort(sy[i].begin(), sy[i].end());
	}
	
	MaxY[U + 1] = -1;
	for (int x = U; x >= 1; --x) {
		MaxY[x] = MaxY[x + 1];
		if (sx[x].size()) 
			MaxY[x] = max(MaxY[x], sx[x].back());
	}
	
	MinY[0] = U + 1;
	for (int x = 1; x <= U; ++x) {
		MinY[x] = MinY[x - 1];
		if (sx[x].size()) 
			MinY[x] = min(MinY[x], sx[x][0]);
	}
	
	MaxX[U + 1] = -1;
	for (int y = U; y >= 1; --y) {
		MaxX[y] = MaxX[y + 1];
		if (sy[y].size()) 
			MaxX[y] = max(MaxX[y], sy[y].back());
	}
	
	MinX[0] = U + 1;
	for (int y = 1; y <= U; ++y) {
		MinX[y] = MinX[y - 1];
		if (sy[y].size()) 
			MinX[y] = min(MinX[y], sy[y][0]);
	}
	
	for (int i = 1; i <= U; ++i)
		for (int j = U; j >= 1; --j) 
			S[i][j] = S[i - 1][j] + S[i][j + 1] - S[i - 1][j + 1] + f[i][j];
		
	for (int i = U; i >= 1; --i)
		for (int j = 1; j <= U; ++j) 
			S_[i][j] = S_[i + 1][j] + S_[i][j - 1] - S_[i + 1][j - 1] + f[i][j];	

	int i1, j1;
	for (int i = 1; i <= U; ++i)
		for (int j = U; j >= 1; --j) {
			i1 = min(i, MinX[j - 1]);
			j1 = max(j, MaxY[i + 1]);
			dp[i][j] = S[i][j] + dp[i1][j1];
		}	
			
	for (int i = U; i >= 1; --i)
		for (int j = 1; j <= U; ++j) {
			i1 = max(i, MaxX[j + 1]);
			j1 = min(j, MinY[i - 1]);
			dp_[i][j] = S_[i][j] + dp_[i1][j1];
		}		

	for (int i = 1; i <= n; ++i) {
		cout << n - 1 + dp[x[i]][y[i]] - 1 + dp_[x[i]][y[i]] - 1 << "\n";
	}
}

Compilation message (stderr)

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

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