제출 #532184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
532184		Sohsoh84	섬 항해 (CEOI13_adriatic)	C++17	80 / 100	2037 ms	60408 KiB

adriatic

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 0 / 20