#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<pair<ll, ll>>
#define vpp vector<pair<ll, pair<ll, ll>>>
#define pp pair<ll, ll>
#define qi queue<ll>
#define qp queue<pp>
#define pqi priority_queue<ll>
#define pqp priority_queue<pp>
#define mi map<ll, ll>
#define mpi map<pp, ll>
#define mip map<ll, pp>
#define mp map<pp, pp>
#define mb map<ll, bool>
#define si set<ll>
#define sp set<pp>
#define sc set<char>
#define mod 1000000007
#define inf INT_MAX
#define all(x) (x).begin(), (x).end()
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n;
cin >> n;
vp a(n);
vc type(n);
vector<pair<pp, ll>> north, south, east, west;
map<ll, vp> diag;
map<ll, vp> diag2;
map<ll, vp> vert;
map<ll, vp> hor;
for(int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second >> type[i];
if(type[i] == 'N') {
north.push_back({a[i], i});
}
else if(type[i] == 'S') {
south.push_back({a[i], i});
}
else if(type[i] == 'W') {
west.push_back({a[i], i});
}
else {
east.push_back({a[i], i});
}
auto[x, y] = a[i];
ll d = x + y;
if(type[i] == 'E' || type[i] == 'S') {
diag[d].push_back({y, i});
}
else {
diag2[d].push_back({y, i});
}
if(type[i] == 'W' || type[i] == 'E') {
hor[y].push_back({x, i});
}
else {
vert[x].push_back({y, i});
}
}
vector<pair<ll, pp>> deaths;
for(auto&[d, v] : diag) {
sort(all(v));
stack<ll> st;
for(int i = 0; i < v.size(); i++) {
ll ind1 = v[i].second;
if(type[ind1] == 'S') {
st.push(ind1);
continue;
}
if(st.size() == 0) continue;
ll ind2 = st.top();
st.pop();
ll time = abs(a[ind1].first - a[ind2].first);
deaths.push_back({time, {ind1, ind2}});
}
}
for(auto&[d, v] : diag2) {
sort(all(v));
stack<ll> st;
for(int i = 0; i < v.size(); i++) {
ll ind1 = v[i].second;
if(type[ind1] == 'W') {
st.push(ind1);
continue;
}
if(st.size() == 0) continue;
ll ind2 = st.top();
st.pop();
ll time = abs(a[ind1].first - a[ind2].first);
deaths.push_back({time, {ind1, ind2}});
}
}
for(auto&[d, v] : vert) {
sort(all(v));
stack<ll> st;
for(int i = 0; i < v.size(); i++) {
ll ind1 = v[i].second;
if(type[ind1] == 'S') {
st.push(ind1);
continue;
}
if(st.size() == 0) continue;
ll ind2 = st.top();
st.pop();
ll time = abs(a[ind1].second - a[ind2].second) / 2;
deaths.push_back({time, {ind1, ind2}});
}
}
for(auto&[d, v] : hor) {
sort(all(v));
stack<ll> st;
for(int i = 0; i < v.size(); i++) {
ll ind1 = v[i].second;
if(type[ind1] == 'E') {
st.push(ind1);
continue;
}
if(st.size() == 0) continue;
ll ind2 = st.top();
st.pop();
ll time = abs(a[ind1].first - a[ind2].first) / 2;
deaths.push_back({time, {ind1, ind2}});
}
}
sort(all(deaths));
si left;
for(int i = 0; i < n; i++) left.insert(i);
for(int i = 0; i < deaths.size();) {
ll curTime = deaths[i].first;
si del;
while(i < deaths.size() && deaths[i].first == curTime) {
ll ind1 = deaths[i].second.first, ind2 = deaths[i].second.second;
if(!left.count(ind1) || !left.count(ind2)) {
i++;
continue;
}
del.insert(ind1);
del.insert(ind2);
i++;
}
for(auto x : del) left.erase(x);
}
for(auto x : left) cout << x + 1 << '\n';
return 0;
}
/*
3
4 0 S
2 2 E
0 4 E
5
2 2 E
4 0 S
0 4 E
1 3 S
3 1 S
2
4
0 6 E
2 4 E
4 2 S
6 0 S
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |