oj.uz

Submission #164379

# Submission time Handle Problem Language Result Execution time Memory
164379 2019-11-20T05:45:10 Z frodakcin Adriatic (CEOI13_adriatic) C++11
60 / 100
 356 ms 206484 KB 
#include <cstdio>
#include <cstring>

using ll = long long;

const int MN = 2.5e5 + 100;
const int MX = 2.5e3 + 10;
int N;

int nx[MX][MX], ny[MX][MX];
ll v[MX][MX];
ll f[MN];
struct ISL
{
public:
	int x, y;
	void in(void) {scanf("%d%d", &x, &y);}
	void flip(void) {x = MX - x - 1, y = MX - y - 1;}
};
ISL a[MN];

void solve(void)
{
	memset(nx, -1, sizeof(nx));
	memset(ny, -1, sizeof(ny));
	memset(v, 0, sizeof(v));
	for(int i = 0, x, y;i < N;++i)
		x = a[i].x, y = a[i].y,
		v[x][y] = 1LL,
		nx[x+1][y+1] = x, ny[x-1][y-1] = y;
	for(int i = 0;i < MX;++i)
		for(int j = 0;j < MX;++j)
		{
			if(i && ~nx[i-1][j] && (nx[i-1][j] < nx[i][j] || !~nx[i][j]))
				nx[i][j] = nx[i-1][j];
			if(j && ~nx[i][j-1] && (nx[i][j-1] < nx[i][j] || !~nx[i][j]))
				nx[i][j] = nx[i][j-1];
		}
	for(int i = MX;i >= 0;--i)
		for(int j = MX;j >= 0;--j)
		{
			if(i<MX && ny[i+1][j] > ny[i][j])
				ny[i][j] = ny[i+1][j];
			if(j<MX && ny[i][j+1] > ny[i][j])
				ny[i][j] = ny[i][j+1];
		}
	for(int i = 0;i < MX;++i)
		for(int j = 0;j < MX;++j)
		{
			if(!~nx[i][j] || nx[i][j] > i) nx[i][j] = i;
			if(ny[i][j] < j) ny[i][j] = j;
		}
	for(int i = 0;i < MX;++i)
	{
		for(int j = MX-2;j >= 0;--j)
			v[i][j] += v[i][j+1];
		if(i)
			for(int j = 0;j < MX;++j)
				v[i][j] += v[i-1][j];
	}
	for(int i = 0;i < MX;++i)
		for(int j = MX;j >= 0;--j)
			if(v[i][j])
				v[i][j] += v[nx[i][j]][ny[i][j]];
	for(int i = 0;i < N;++i)
		f[i] += v[a[i].x][a[i].y] - 1;
}

int main(void)
{
	scanf("%d", &N);
	for(int i = 0;i < N;++i)
		a[i].in();
	solve();
	for(int i = 0;i < N;++i)
		a[i].flip();
	solve();
	for(int i = 0;i < N;++i)
		printf("%lld\n", f[i]+N-1);
	return 0;
}

Compilation message

adriatic.cpp: In function 'int main()':
adriatic.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
adriatic.cpp: In member function 'void ISL::in()':
adriatic.cpp:17:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  void in(void) {scanf("%d%d", &x, &y);}
                 ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 98936 KB Output is correct
2 Correct 239 ms 99064 KB Output is correct
3 Correct 235 ms 98936 KB Output is correct
4 Correct 220 ms 98992 KB Output is correct
5 Correct 240 ms 99092 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 99028 KB Output is correct
2 Correct 241 ms 99064 KB Output is correct
3 Correct 242 ms 99064 KB Output is correct
4 Correct 222 ms 98936 KB Output is correct
5 Correct 236 ms 99068 KB Output is correct
6 Correct 247 ms 99064 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 99068 KB Output is correct
2 Correct 244 ms 99168 KB Output is correct
3 Correct 250 ms 99192 KB Output is correct
4 Correct 225 ms 99192 KB Output is correct
5 Correct 240 ms 99104 KB Output is correct
6 Correct 269 ms 99192 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 307 ms 200900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 356 ms 206484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -