oj.uz

Submission #362890

# Submission time Handle Problem Language Result Execution time Memory
362890 2021-02-04T16:06:03 Z GioChkhaidze Adriatic (CEOI13_adriatic) C++14
100 / 100
 308 ms 114668 KB 
#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

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 98924 KB Output is correct
2 Correct 128 ms 98924 KB Output is correct
3 Correct 134 ms 98924 KB Output is correct
4 Correct 136 ms 98672 KB Output is correct
5 Correct 146 ms 98796 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 102252 KB Output is correct
2 Correct 145 ms 102564 KB Output is correct
3 Correct 145 ms 102508 KB Output is correct
4 Correct 155 ms 98924 KB Output is correct
5 Correct 135 ms 99308 KB Output is correct
6 Correct 146 ms 101228 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 104424 KB Output is correct
2 Correct 148 ms 104860 KB Output is correct
3 Correct 150 ms 104668 KB Output is correct
4 Correct 145 ms 99604 KB Output is correct
5 Correct 152 ms 99852 KB Output is correct
6 Correct 180 ms 105016 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 105836 KB Output is correct
2 Correct 151 ms 105664 KB Output is correct
3 Correct 167 ms 105708 KB Output is correct
4 Correct 163 ms 100716 KB Output is correct
5 Correct 144 ms 101012 KB Output is correct
6 Correct 176 ms 105836 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 113468 KB Output is correct
2 Correct 302 ms 113500 KB Output is correct
3 Correct 303 ms 113516 KB Output is correct
4 Correct 308 ms 109840 KB Output is correct
5 Correct 252 ms 109480 KB Output is correct
6 Correct 276 ms 114668 KB Output is correct
7 Correct 287 ms 114560 KB Output is correct