Submission #1204342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204342		NK_	Naval battle (CEOI24_battle)	C++20	76 / 100	327 ms	52032 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

#define f first
#define s second
#define mp make_pair

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
template<class T> using V = vector<T>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
using vi = V<int>;
using vl = V<ll>;
using vpl = V<pl>;
using vpi = V<pi>;

const int INF = 1e9 + 10;

struct T {
	array<int, 3> ans = {INF, -1, -1}; // time of crash
	int l = -INF, lx = -1; // ship coming from left (max)
	int r = INF, rx = -1; // ship coming from right (min)
};


struct Seg {
	T ID; 
	V<T> seg; int n; T cmb(T a, T b) {
		T c; c.ans = min(a.ans, b.ans);
		if (b.lx != -1) c.l = b.l, c.lx = b.lx;
		else c.l = a.l, c.lx = a.lx;

		if (a.rx != -1) c.r = a.r, c.rx = a.rx;
		else c.r = b.r, c.rx = b.rx;

		c.ans = min(a.ans, b.ans);
		if (b.r - a.l < c.ans[0]) c.ans = {b.r - a.l, a.lx, b.rx};
		return c;
	}

	void init(int _n) {
		for(n = 1; n < _n;) n *= 2;
		seg.assign(2 * n, ID);
	}

	void pull(int p) { seg[p] = cmb(seg[2 * p], seg[2 * p + 1]); }

	void upd(int p, T x) {
		seg[p += n] = x;
		for(p /= 2; p; p /= 2) pull(p);
	}

	array<int, 3> get() { return seg[1].ans; }
};


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	vi X(N), Y(N); V<char> D(N);
	for(int i = 0; i < N; i++) {
		cin >> X[i] >> Y[i] >> D[i];
	}

	if (N <= 5000) {
		V<array<int, 3>> E;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if (D[i] == D[j]) continue;

				if (D[i] == 'S' && D[j] == 'N') {
					if (X[i] == X[j] && Y[i] < Y[j]) {
						int t = Y[j] - Y[i];
						E.pb({t / 2, i, j});
					}
				} 

				if (D[i] == 'E' && D[j] == 'W') {
					if (Y[i] == Y[j] && X[i] < X[j]) {
						int t = X[j] - X[i];
						E.pb({t / 2, i, j});
					}
				}


				if (D[i] == 'S' && D[j] == 'W') {
					if (X[i] - Y[i] == X[j] - Y[j] && X[i] < X[j]) {
						int t = X[j] - X[i];
						E.pb({t, i, j});
					}
				}

				if (D[i] == 'N' && D[j] == 'E') {
					if (X[i] - Y[i] == X[j] - Y[j] && X[i] > X[j]) {
						int t = X[i] - X[j];
						E.pb({t, i, j});
					}
				}

				if (D[i] == 'N' && D[j] == 'W') {
					if (X[i] + Y[i] == X[j] + Y[j] && X[i] < X[j]) {
						int t = X[j] - X[i];
						E.pb({t, i, j});
					}
				}

				if (D[i] == 'S' && D[j] == 'E') {
					if (X[i] + Y[i] == X[j] + Y[j] && X[i] > X[j]) {
						int t = X[i] - X[j];
						E.pb({t, i, j});
					}
				}
			}
		}	

		sort(begin(E), end(E));
		vi dead(N, 0);
		for(int i = 0; i < sz(E); i++) {
			int j = i; vi upd;
			while(j < sz(E) && E[i][0] == E[j][0]) {
				auto [t, x, y] = E[j];
				// cout << t << " -> " << x << " " << y << endl;
				if (!dead[x] && !dead[y]) {
					upd.pb(x); upd.pb(y);
				}
				j++;
			}

			i = j - 1;

			for(auto& x : upd) dead[x] = 1;
		}
		
		for(int i = 0; i < N; i++) if (!dead[i]) cout << i + 1 << nl;
	} else {
		map<int, int> to;
		for(int i = 0; i < N; i++) to[X[i] + Y[i]]++;
		int M = 0; for(auto& [k, v] : to) v = M++;

		V<vpi> G(M);

		for(int i = 0; i < N; i++) {
			G[to[X[i] + Y[i]]].pb(mp(X[i], i));
		}

		V<Seg> st(M);
		pq<array<int, 3>> q;
		for(int i = 0; i < M; i++) {
			sort(begin(G[i]), end(G[i]));
			int n = sz(G[i]);
			st[i].init(n);
			for(int x = 0; x < n; x++) {
				if (D[G[i][x].s] == 'S') {
					st[i].upd(x, T{{INF, -1, -1}, -INF, -1, G[i][x].f, G[i][x].s});
				} else {
					st[i].upd(x, T{{INF, -1, -1}, G[i][x].f, G[i][x].s, INF, -1});
				}
			}
			// cout << i << endl;

			q.push(st[i].get());
		}

		auto rem = [&](int d, int x) {
			int pos = lower_bound(begin(G[d]), end(G[d]), mp(X[x], x)) - begin(G[d]);
			st[d].upd(pos, st[d].ID);
		};

		vi dead(N, INF);
		while(sz(q)) {
			auto [t, x, y] = q.top(); q.pop();
			if (t == INF) break;

			// cout << t << " " << x << " " << y << endl;

			if (dead[x] < t || dead[y] < t) continue;
			dead[x] = min(dead[x], t);
			dead[y] = min(dead[y], t);

			int d = to[X[x] + Y[x]];
			rem(d, x); rem(d, y);
			q.push(st[d].get());
		}

		for(int i = 0; i < N; i++) if (dead[i] == INF) cout << i + 1 << nl;
	}


	exit(0-0);
}

// Breathe In, Breathe Out
	

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 12 / 12
• Subtask 3: 8 / 8
• Subtask 4: 11 / 11
• Subtask 5: 9 / 9
• Subtask 6: 30 / 30
• Subtask 7: 0 / 24