oj.uz

Submission #164386

# Submission time Handle Problem Language Result Execution time Memory
164386 2019-11-20T06:31:50 Z frodakcin Adriatic (CEOI13_adriatic) C++11
100 / 100
 263 ms 56868 KB 
#include <cstdio>
#include <cstring>
#include <cassert>

using ll = long long;

void min(int* a, int b) {return (void)(~b&&(b<*a||!~*a)?*a=b:0);}
void max(int* a, int b) {return (void)(*a<b?*a=b:0);}
int min(int a, int b) {return ~b&&b<a?b:a;}
int max(int a, int b) {return a<b?b:a;}
const int MN = 2.5e5 + 100;
const int MX = 2.5e3 + 10;
int N;

int nx[MX], ny[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,
		min(nx+(y+1), x), max(ny+(x-1), y);
	for(int i = 0;i+1 < MX;++i)
		max(ny+(MX-i-2), ny[MX-i-1]),
			min(nx+(i+1), nx[i]);
	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-1;j >= 0;--j)
			if(v[i][j])
				v[i][j] += v[min(i, nx[j])][max(j, ny[i])];
	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:57: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:22: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 127 ms 49624 KB Output is correct
2 Correct 126 ms 49784 KB Output is correct
3 Correct 127 ms 49656 KB Output is correct
4 Correct 114 ms 49656 KB Output is correct
5 Correct 129 ms 49632 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 49760 KB Output is correct
2 Correct 129 ms 49784 KB Output is correct
3 Correct 132 ms 49744 KB Output is correct
4 Correct 113 ms 49660 KB Output is correct
5 Correct 129 ms 49660 KB Output is correct
6 Correct 191 ms 49656 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 49808 KB Output is correct
2 Correct 130 ms 49796 KB Output is correct
3 Correct 136 ms 49812 KB Output is correct
4 Correct 117 ms 49784 KB Output is correct
5 Correct 151 ms 49784 KB Output is correct
6 Correct 150 ms 49784 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 50480 KB Output is correct
2 Correct 140 ms 50484 KB Output is correct
3 Correct 146 ms 50428 KB Output is correct
4 Correct 127 ms 50424 KB Output is correct
5 Correct 150 ms 50500 KB Output is correct
6 Correct 166 ms 50428 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 55716 KB Output is correct
2 Correct 240 ms 56568 KB Output is correct
3 Correct 253 ms 56568 KB Output is correct
4 Correct 213 ms 56552 KB Output is correct
5 Correct 219 ms 56568 KB Output is correct
6 Correct 234 ms 56868 KB Output is correct
7 Correct 232 ms 56824 KB Output is correct