oj.uz

Submission #532184

# Submission time Handle Problem Language Result Execution time Memory
532184 2022-03-02T11:39:02 Z Sohsoh84 Adriatic (CEOI13_adriatic) C++17
80 / 100
 2000 ms 60408 KB 
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<int, int> pll;
typedef pair<pll, pll> rect;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;
#define debugr(x)		cerr << #x << ": " << x.X.X << sep << x.X.Y << ", " << x.Y.X << sep << x.Y.Y << endl;

constexpr ll MAXD = 2500 + 10;
constexpr ll MAXN = 3e5 + 10;

int ps[MAXD][MAXD], n, ss[MAXD][MAXD];
bool B[MAXD][MAXD];
pll s, P[MAXN];


inline bool inside(rect a, pll b) {
	return a.X.X <= b.X && b.X <= a.Y.X && a.X.Y <= b.Y && b.Y <= a.Y.Y;
}

inline int sum(rect a) {
        return ps[a.Y.X][a.Y.Y] - ps[a.Y.X][a.X.Y - 1] - ps[a.X.X - 1][a.Y.Y] + ps[a.X.X - 1][a.X.Y - 1] - inside(a, s); //
}

inline int bfs_try_xy(rect a) {
	int ans = 0;
	while (ss[a.Y.X + 1][a.X.Y + ans + 1] > 0)
		ans++;

	return ans;
}

inline int bfs_try_yy(rect a) {
	int ans = 0;
	while (ps[a.X.X - 1][a.Y.Y - ans - 1] > 0)
		ans++;

	return ans;
}

inline int bfs_try_xx(rect a) {
	int ans = 0;
	while (ss[a.X.X + ans + 1][a.Y.Y + 1] > 0)
		ans++;

	return ans;
}

inline int bfs_try_yx(rect a) {
	int ans = 0;
	while (ps[a.Y.X - ans - 1][a.X.Y - 1] > 0)
		ans++;

	return ans;
}

inline ll solve() {
	rect a = {{1, s.Y}, {s.X, MAXD - 2}}, b = {{s.X, 1}, {MAXD - 2, s.Y}};	
	int ans = n - 1 + sum(a) + sum(b);

	bool is_alive_a = sum(a), is_alive_b = sum(b);
	while (is_alive_a || is_alive_b) {
		rect prev_a = a, prev_b = b;
		if (is_alive_a) {
			a.X.Y += bfs_try_xy(prev_a);	
			a.Y.X -= bfs_try_yx(prev_a);
		}

		if (is_alive_b) {
			b.X.X += bfs_try_xx(prev_b);		
		 	b.Y.Y -= bfs_try_yy(prev_b);
		}

		int x = sum(a);
		int y = sum(b);

		if (x <= 0) is_alive_a = false;
		if (y <= 0) is_alive_b = false;
		if (is_alive_a) ans += sum(a);
		if (is_alive_b) ans += sum(b); 
	}

	return ans;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		B[x][y] = true;
		P[i] = {x, y};
	}

	for (int i = 1; i < MAXD; i++) {
		for (int j = 1; j < MAXD; j++) {
			ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + B[i][j];
		}
	}

	for (int i = MAXD - 2; i >= 0; i--) {
		for (int j = MAXD - 2; j >= 0; j--) {
			ss[i][j] = ss[i + 1][j] + ss[i][j + 1] - ss[i + 1][j + 1] + B[i][j];
		}
	}

	for (int i = 1; i <= n; i++) {
		s = P[i];
		cout << solve() << endl;
	}
	return 0;
}

Compilation message

adriatic.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
adriatic.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 49976 KB Output is correct
2 Correct 66 ms 50012 KB Output is correct
3 Correct 65 ms 50000 KB Output is correct
4 Correct 63 ms 49664 KB Output is correct
5 Correct 65 ms 49816 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 53192 KB Output is correct
2 Correct 106 ms 53480 KB Output is correct
3 Correct 95 ms 53356 KB Output is correct
4 Correct 62 ms 49856 KB Output is correct
5 Correct 87 ms 50244 KB Output is correct
6 Correct 109 ms 52212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 55312 KB Output is correct
2 Correct 167 ms 55620 KB Output is correct
3 Correct 173 ms 55508 KB Output is correct
4 Correct 71 ms 50380 KB Output is correct
5 Correct 164 ms 50628 KB Output is correct
6 Correct 255 ms 55808 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 56496 KB Output is correct
2 Correct 581 ms 56432 KB Output is correct
3 Correct 576 ms 56496 KB Output is correct
4 Correct 104 ms 51332 KB Output is correct
5 Correct 532 ms 52008 KB Output is correct
6 Correct 1166 ms 56516 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 60408 KB Time limit exceeded
2 Halted 0 ms 0 KB -