이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=2e9;
const int N=2e5+10, dx[]={0, 0, 1, -1}, dy[]={-1, 1, 0, 0};
const string dir="NSEW";
struct DS{
map<int, array<int, 3>> mp;
set<array<int, 3>> st;
set<pair<int, pair<array<int, 3>, array<int, 3>>>> d;
void add(int x, int i, int t){
mp[i]={x, i, t};
st.insert({x, i, t});
}
void build(){
for (auto it=st.begin(); it!=st.end() && next(it)!=st.end(); ++it){
if (it->begin()[2]==0 && next(it)->begin()[2]==1){
d.insert({next(it)->begin()[0]-it->begin()[0], {*it, *next(it)}});
}
}
}
void erase(pair<array<int, 3>, array<int, 3>> p){
auto it=st.find(p.first);
d.erase({p.second[0]-p.first[0], p});
it=st.erase(it);
it=st.erase(it);
if (it!=st.begin() && it!=st.end() && prev(it)->begin()[2]==0 && it->begin()[2]==1){
d.insert({it->begin()[0]-prev(it)->begin()[0], {*prev(it), *it}});
}
}
void erase(int i){
auto it=st.find(mp[i]);
if (it==st.end()) return;
if (it!=st.begin() && prev(it)->begin()[2]==0 && it->begin()[2]==1){
d.erase({it->begin()[0]-prev(it)->begin()[0], {*prev(it), *it}});
}
if (it!=st.end() && it->begin()[2]==0 && next(it)->begin()[2]==1){
d.erase({next(it)->begin()[0]-it->begin()[0], {*it, *next(it)}});
}
it=st.erase(it);
if (it!=st.begin() && it!=st.end() && prev(it)->begin()[2]==0 && it->begin()[2]==1){
d.insert({it->begin()[0]-prev(it)->begin()[0], {*prev(it), *it}});
}
}
int get(){
if (d.empty()) return inf;
return d.begin()->first;
}
};
int n, x[N], y[N], d[N], t[N], ans[N];
char c[N];
// 23, 10, 20, 13, 30, 12
map<int, DS> mp[4][4];
vector<DS> v;
vector<int> id[N];
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i=1; i<=n; ++i){
cin >> x[i] >> y[i] >> c[i]; ans[i]=1;
t[i]=2e9;
d[i]=dir.find(c[i]);
}
for (int i=1; i<=n; ++i){
if (d[i]==0){
mp[1][0][x[i]].add(y[i]/2, i, 1);
mp[2][0][x[i]-y[i]].add(y[i], i, 1);
mp[3][0][x[i]+y[i]].add(y[i], i, 1);
}
if (d[i]==1){
mp[1][0][x[i]].add(y[i]/2, i, 0);
mp[1][3][x[i]-y[i]].add(y[i], i, 0);
mp[1][2][x[i]+y[i]].add(y[i], i, 0);
}
if (d[i]==2){
mp[2][3][y[i]].add(x[i]/2, i, 0);
mp[2][0][x[i]-y[i]].add(y[i], i, 0);
mp[1][2][x[i]+y[i]].add(y[i], i, 1);
}
if (d[i]==3){
mp[2][3][y[i]].add(x[i]/2, i, 1);
mp[1][3][x[i]-y[i]].add(y[i], i, 1);
mp[3][0][x[i]+y[i]].add(y[i], i, 0);
}
}
for (int i=0; i<4; ++i) for (int j=0; j<4; ++j){
for (auto &k:mp[i][j]) v.push_back(k.second);
}
set<pair<int, int>> st;
for (int i=0; i<(int)v.size(); ++i){
for (auto &j:v[i].st) id[j[1]].push_back(i);
v[i].build();
st.emplace(v[i].get(), i);
}
while (st.size()){
int val=st.begin()->first;
if (val==inf) break;
vector<int> vv;
for (auto it=st.begin(); it!=st.end(); ++it){
if (it->first!=val) break;
vv.push_back(it->second);
}
set<int> del;
for (int i:vv){
while (v[i].get()==val){
st.erase({v[i].get(), i});
auto p=v[i].d.begin()->second;
v[i].erase(p);
del.insert(p.first[1]); del.insert(p.second[1]);
st.erase({v[i].get(), i});
}
}
for (int i:del){
ans[i]=0;
for (int j:id[i]){
st.erase({v[j].get(), j});
v[j].erase(i);
st.insert({v[j].get(), j});
}
}
}
for (int i=1; i<=n; ++i) if (ans[i]) cout << i << '\n';
return 0;
}
# | 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... |