#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
map<ll,set<pair<ll,ll>>>mp[6];
ll n,a,b,c;
char ch;
bool bad[200007];
set<pair<ll,pair<ll,ll>>>s;
vector<pair<char,pair<ll,ll>>>v;
bool czy(ll x,ll y,ll idx){
if(v[x].ff>v[y].ff)swap(x,y);
if(idx==0){
x=v[x].ss.ss-v[y].ss.ss;
}
else{
x=v[x].ss.ff-v[y].ss.ff;
}
if(idx==0 || idx==1)if(x%2)return 0;
if(idx==0) return x>0;
return x<0;
}
ll f2(ll x,ll y,ll z){
if(z==0)return x;
if(z==1)return y;
if(z/2==1)return x+y;
return x-y;
}
void f(ll idx,ll x){
pair<ll,ll>pom=v[x].ss;
a=pom.ff;
b=pom.ss;
ch=v[x].ff;
auto it=mp[idx][f2(a,b,idx)].lower_bound({a*((bool)idx)+b*(!(bool)idx),x});
if(it!=mp[idx][f2(a,b,idx)].begin() && v[(*prev(it)).ss].ff!=ch){
ll curr=(*prev(it)).ss;
if(czy(x,curr,idx))
s.erase({max(abs(a-v[curr].ss.ff),abs(b-v[curr].ss.ss))/(1+(idx==0 || idx==1)),{min(curr,x),max(curr,x)}});
}
if(it!=--mp[idx][f2(a,b,idx)].end() && v[(*next(it)).ss].ff!=ch){
ll curr=(*next(it)).ss;
if(czy(x,curr,idx))
s.erase({max(abs(a-v[curr].ss.ff),abs(b-v[curr].ss.ss))/(1+(idx==0 || idx==1)),{min(curr,x),max(curr,x)}});
}
if(it!=mp[idx][f2(a,b,idx)].begin() && it!=--mp[idx][f2(a,b,idx)].end() && v[(*next(it)).ss].ff!=v[(*prev(it)).ss].ff){
ll curr=(*prev(it)).ss;
x=(*next(it)).ss;
if(czy(x,curr,idx))
s.insert({max(abs(v[x].ss.ff-v[curr].ss.ff),abs(v[x].ss.ss-v[curr].ss.ss))/(1+(idx==0 || idx==1)),{min(curr,x),max(curr,x)}});
}
}
void us(ll x){
pair<ll,ll>pom=v[x].ss;
a=pom.ff;
b=pom.ss;
ch=v[x].ff;
if(ch=='N' || ch=='S'){
f(0,x);
mp[0][a].erase({a,x});
}
else{f(1,x);
mp[1][b].erase({a,x});
}
if(ch=='N' || ch=='W'){f(2,x);
mp[2][a+b].erase({a,x});
}
else{f(3,x);
mp[3][a+b].erase({a,x});
}
if(ch=='N' || ch=='E'){f(4,x);
mp[4][a-b].erase({a,x});
}
else{f(5,x);
mp[5][a-b].erase({a,x});
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(ll i=0;i<n;i++){
cin>>a>>b>>ch;
v.pb({ch,{a,b}});
if(ch=='N' || ch=='S'){
mp[0][a].insert({b,i});
}
else{
mp[1][b].insert({a,i});
}
if(ch=='N' || ch=='W'){
mp[2][a+b].insert({a,i});
}
else{
mp[3][a+b].insert({a,i});
}
if(ch=='N' || ch=='E'){
mp[4][a-b].insert({a,i});
}
else{
mp[5][a-b].insert({a,i});
}
}
for(ll i=0;i<6;i++){
for(auto j : mp[i]){
for(auto it=j.ss.begin();it!=j.ss.end() && it!=--j.ss.end();it++){
if(v[(*next(it)).ss].ff!=v[(*it).ss].ff){
ll curr=(*it).ss;
ll x=(*next(it)).ss;
if(czy(x,curr,i))
s.insert({max(abs(v[x].ss.ff-v[curr].ss.ff),abs(v[x].ss.ss-v[curr].ss.ss))/(1+(i==0 || i==1)),{min(curr,x),max(curr,x)}});
}
}
}
}
while(s.size()){
ll ak=(*s.begin()).ff;
vector<ll>vak;
for(auto it=s.begin();it!=s.end() && (*it).ff==ak;it++){
vak.pb((*it).ss.ff);
vak.pb((*it).ss.ss);
}
for(ll i : vak){
if(!bad[i]){
bad[i]=1;
us(i);
}
}
}
for(ll i=0;i<n;i++)if(!bad[i])cout<<i+1<<"\n";
}
# | 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... |