Submission #1195386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195386		franuch	Naval battle (CEOI24_battle)	C++20	100 / 100	1084 ms	113608 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<unordered_map<ll, map<ll, ll>>> Con;
#define sz(a) (ll)a.size()
#define all(a) a.begin(), a.end()
#define vc vector
#define pub push_back
#define pob pop_back
#define st first
#define nd second
const ll INF = 1e18;
const ll bINF = 1e10;

struct Tree {
	ll base;
	vc<pll> t;
	Tree() = default;
	Tree(ll n) {
		base = 1;
		while (base < n)
			base *= 2;
		t.assign(2 * base, {INF, 0});
		for (ll i = 0; i < base; i++)
			t[i + base].nd = i;
	}
	void set(ll i, ll x) {
		i += base;
		t[i].st = x;
		i /= 2;
		while (i >= 1) {
			t[i] = min(t[2 * i], t[2 * i + 1]);
			i /= 2;
		}
	}

	pll get() {
		return t[1];
	}
};

struct Ship {
	ll x, y, dir;
};

ll n;
vc<Ship> a;
vc<vc<ll>> c;
Con hor(2), ver(2), ascu(2), ascd(2), desu(2), desd(2);
Tree tree;

void input() {
	cin >> n;
	a.resize(n);
	for (auto &ai : a) {
		cin >> ai.x >> ai.y;
		char dir;
		cin >> dir;
		if (dir == 'N')
			ai.dir = 1;
		else if (dir == 'S')
			ai.dir = 0;
		else if (dir == 'E')
			ai.dir = 2;
		else
			ai.dir = 3;
	}
}

void updd(Con *con, ll i, ll j, ll k, ll id) {
	ll d = INF;
	if (i == 0) {
		auto mp = con->at(1).find(j);
		if (mp != con->at(1).end()) {
			auto find = mp->nd.upper_bound(k);
			if (find != mp->nd.end()) {
				if ((--(con->at(0)[j].lower_bound(find->st)))->nd == id)
					d = find->st - k;
			}
		}
	} else {
		auto mp = con->at(0).find(j);
		if (mp != con->at(0).end()) {
			auto find = mp->nd.lower_bound(k);
			if (find != mp->nd.begin()) {
				find--;
				if (con->at(1)[j].upper_bound(find->st)->nd == id)
					d = k - find->st;
			}
		}
	}
	if (con == &hor)
		c[0][id] = d;
	else if (con == &ver)
		c[1][id] = d;
	else if (con == &ascu or con == &ascd)
		c[2][id] = d;
	else
		c[3][id] = d;
	
	tree.set(id, min(min(c[0][id] / 2, c[1][id] / 2), min(c[2][id] / 2, c[3][id] / 2)));
}

void updall(Con &con) {
	for (ll i = 0; i < 2; i++)
		for (auto &[j, mp] : con[i])
			for (auto &[k, id] : mp)
				updd(&con, i, j, k, id);
}

struct Sav {
	Con *con;
	ll i, j, k, id;
};

map<ll, ll> emp;
pair<Sav, Sav> rem(Con *con, ll i, ll j, ll k) {
	vc<map<ll, ll> *> mp(2);
	mp[i] = &con->at(i)[j];
	mp[i]->erase(k);
	auto fmp = con->at(i ^ 1).find(j);
	if (fmp != con->at(i ^ 1).end())
		mp[i ^ 1] = &(fmp->nd);
	else
		mp[i ^ 1] = &emp;
	
	pair<Sav, Sav> ret = {{nullptr, -1, -1, -1, -1}, {nullptr, -1, -1, -1, -1}};
	auto find = mp[0]->lower_bound(k);
	if (find != mp[0]->begin()) {
		find--;
		ret.st = {con, 0, j, find->st, find->nd};
	}
	find = mp[1]->upper_bound(k);
	if (find != mp[1]->end())
		ret.nd = {con, 1, j, find->st, find->nd};
	return ret;
}

void prepro() {
	c.assign(4, vc<ll>(n, INF));
	for (ll i = 0; i < n; i++) {
		ll x = a[i].x;
		ll y = a[i].y;
		ll dir = a[i].dir;
		if (dir == 0) {
			ver[0][x][y] = i;
			ascu[0][x - y][x + y] = i;
			desu[1][x + y][x - y] = i;
		} else if (dir == 1) {
			ver[1][x][y] = i;
			ascd[1][x - y][x + y] = i;
			desd[0][x + y][x - y] = i;
		} else if (dir == 2) {
			hor[0][y][x] = i;
			ascd[0][x - y][x + y] = i;
			desu[0][x + y][x - y] = i;
		} else {
			hor[1][y][x] = i;
			ascu[1][x - y][x + y] = i;
			desd[1][x + y][x - y] = i;
		}
	}
	tree = Tree(n);
	updall(hor);
	updall(ver);
	updall(ascu);
	updall(ascd);
	updall(desu);
	updall(desd);
}

void simulate() {
	vc<bool> sur(n, true);
	while (true) {
		auto p = tree.get();
		if (p.st > bINF)
			break;
		
		ll t = p.st;
		vc<ll> tor;
		while (true) {
			p = tree.get();
			if (p.st != t)
				break;
			tor.pub(p.nd);
			tree.set(p.nd, INF);
		}

		vc<pair<Sav, Sav>> tou;
		for (ll &id : tor) {
			sur[id] = false;
			ll x = a[id].x;
			ll y = a[id].y;
			ll dir = a[id].dir;
			if (dir == 0) {
				tou.pub(rem(&ver, 0, x, y));
				tou.pub(rem(&ascu, 0, x - y, x + y));
				tou.pub(rem(&desu, 1, x + y, x - y));
			} else if (dir == 1) {
				tou.pub(rem(&ver, 1, x, y));
				tou.pub(rem(&ascd, 1, x - y, x + y));
				tou.pub(rem(&desd, 0, x + y, x - y));
			} else if (dir == 2) {
				tou.pub(rem(&hor, 0, y, x));
				tou.pub(rem(&ascd, 0, x - y, x + y));
				tou.pub(rem(&desu, 0, x + y, x - y));
			} else {
				tou.pub(rem(&hor, 1, y, x));
				tou.pub(rem(&ascu, 1, x - y, x + y));
				tou.pub(rem(&desd, 1, x + y, x - y));
			}
		}
		for (auto &p : tou) {
			//cout << p.st.id << " " << p.nd.id << " ";
			{
				auto [con, i, j, k, id] = p.st;
				if (id != -1 and sur[id])
					updd(con, i, j, k, id);
			}
			auto [con, i, j, k, id] = p.nd;
			if (id != -1 and sur[id])
				updd(con, i, j, k, id);
		}
		//cout << "\n";
	}
	for (ll i = 0; i < n; i++)
		if (sur[i])
			cout << i + 1 << "\n";
}

void program() {
	input();
	prepro();
	simulate();
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	program();
	return 0;
}

• 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: 24 / 24