Submission #1207450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207450		byunjaewoo	Naval battle (CEOI24_battle)	C++20	36 / 100	2789 ms	207056 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=200010, INF=1e12;
int n, x[N], y[N], md[N];
char d[N], chk[N];
map<int, set<int>> ud[2], lr[2], d1[2], d2[2], d3[2], d4[2];
map<pair<int, int>, int> udc, lrc, d1c, d2c, d3c, d4c;
set<int> ans;
set<pair<int, int>> st;

int minDist(int k) {
    int ret=INF;
    if(d[k]=='N') {
        {
            auto p=ud[0][x[k]].lower_bound(y[k]);
            if(p!=ud[0][x[k]].begin()) {
                p=prev(p);
                auto q=ud[1][x[k]].lower_bound(y[k]);
                if(q==ud[1][x[k]].begin() || (*prev(q))<(*p)) ret=min(ret, (y[k]-(*p))/2);
            }
        }
        {
            auto p=d2[0][x[k]+y[k]].lower_bound(x[k]);
            if(p!=d2[0][x[k]+y[k]].end()) {
                auto q=d2[1][x[k]+y[k]].upper_bound(x[k]);
                if(q==d2[1][x[k]+y[k]].end() || (*q)>(*p)) ret=min(ret, (*p)-x[k]);
            }
        }
        {
            auto p=d4[0][x[k]-y[k]].lower_bound(x[k]);
            if(p!=d4[0][x[k]-y[k]].begin()) {
                p=prev(p);
                auto q=d4[1][x[k]-y[k]].lower_bound(x[k]);
                if(q==d4[1][x[k]-y[k]].begin() || (*prev(q))<(*p)) ret=min(ret, x[k]-(*p));
            }
        }
    }
    else if(d[k]=='S') {
        {
            auto p=ud[1][x[k]].lower_bound(y[k]);
            if(p!=ud[1][x[k]].end()) {
                auto q=next(ud[0][x[k]].lower_bound(y[k]));
                if(q==ud[0][x[k]].end() || (*q)>(*p)) ret=min(ret, ((*p)-y[k])/2);
            }
        }
        {
            auto p=d1[0][x[k]+y[k]].lower_bound(x[k]);
            if(p!=d1[0][x[k]+y[k]].begin()) {
                p=prev(p);
                auto q=d1[1][x[k]+y[k]].lower_bound(x[k]);
                if(q==d1[1][x[k]+y[k]].begin() || (*prev(q))<(*p)) ret=min(ret, x[k]-(*p));
            }
        }
        {
            auto p=d3[0][x[k]-y[k]].lower_bound(x[k]);
            if(p!=d3[0][x[k]-y[k]].end()) {
                auto q=next(d3[1][x[k]-y[k]].lower_bound(x[k]));
                if(q==d3[1][x[k]-y[k]].end() || (*q)>(*p)) ret=min(ret, (*p)-x[k]);
            }
        }
    }
    else if(d[k]=='E') {
        {
            auto p=lr[0][y[k]].lower_bound(x[k]);
            if(p!=lr[0][y[k]].end()) {
                auto q=next(lr[1][y[k]].lower_bound(x[k]));
                if(q==lr[1][y[k]].end() || (*q)>(*p)) ret=min(ret, ((*p)-x[k])/2);
            }
        }
        {
            auto p=d1[1][x[k]+y[k]].lower_bound(x[k]);
            if(p!=d1[1][x[k]+y[k]].end()) {
                auto q=next(d1[0][x[k]+y[k]].lower_bound(x[k]));
                if(q==d1[0][x[k]+y[k]].end() || (*q)>(*p)) ret=min(ret, (*p)-x[k]);
            }
        }
        {
            auto p=d4[1][x[k]-y[k]].lower_bound(x[k]);
            if(p!=d4[1][x[k]-y[k]].end()) {
                auto q=next(d4[0][x[k]-y[k]].lower_bound(x[k]));
                if(q==d4[0][x[k]-y[k]].end() || (*q)>(*p)) ret=min(ret, (*p)-x[k]);
            }
        }
    }
    else if(d[k]=='W') {
        {
            auto p=lr[1][y[k]].lower_bound(x[k]);
            if(p!=lr[1][y[k]].begin()) {
                p=prev(p);
                auto q=lr[0][y[k]].lower_bound(x[k]);
                if(q==lr[0][y[k]].begin() || (*q)<(*p)) ret=min(ret, (x[k]-(*p))/2);
            }
        }
        {
            auto p=d2[1][x[k]+y[k]].lower_bound(x[k]);
            if(p!=d2[1][x[k]+y[k]].begin()) {
                p=prev(p);
                auto q=d2[0][x[k]+y[k]].lower_bound(x[k]);
                if(q==d2[0][x[k]+y[k]].begin() || (*q)<(*p)) ret=min(ret, x[k]-(*p));
            }
        }
        {
            auto p=d3[1][x[k]-y[k]].lower_bound(x[k]);
            if(p!=d3[1][x[k]-y[k]].begin()) {
                p=prev(p);
                auto q=d3[0][x[k]-y[k]].lower_bound(x[k]);
                if(q==d3[0][x[k]-y[k]].begin() || (*q)<(*p)) ret=min(ret, x[k]-(*p));
            }
        }
    }
    return ret;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>x[i]>>y[i]>>d[i];
        if(d[i]=='N' || d[i]=='S') ud[d[i]=='N'][x[i]].insert(y[i]), udc[{x[i], y[i]}]=i;
        if(d[i]=='E' || d[i]=='W') lr[d[i]=='E'][y[i]].insert(x[i]), lrc[{y[i], x[i]}]=i;
        if(d[i]=='S' || d[i]=='E') d1[d[i]=='S'][x[i]+y[i]].insert(x[i]), d1c[{x[i]+y[i], x[i]}]=i;
        if(d[i]=='N' || d[i]=='W') d2[d[i]=='N'][x[i]+y[i]].insert(x[i]), d2c[{x[i]+y[i], x[i]}]=i;
        if(d[i]=='S' || d[i]=='W') d3[d[i]=='S'][x[i]-y[i]].insert(x[i]), d3c[{x[i]-y[i], x[i]}]=i;
        if(d[i]=='N' || d[i]=='E') d4[d[i]=='N'][x[i]-y[i]].insert(x[i]), d4c[{x[i]-y[i], x[i]}]=i;
    }
    for(int i=1; i<=n; i++) md[i]=minDist(i), st.insert({md[i], i}), ans.insert(i);
    while(!st.empty()) {
        if(st.begin()->first==INF) break;
        int tmp=st.begin()->first;
        vector<int> vec;
        while(!st.empty() && st.begin()->first==tmp) {
            vec.push_back(st.begin()->second), chk[st.begin()->second]=true;
            ans.erase(st.begin()->second), st.erase(st.begin());
        }
        for(int i:vec) {
            if(d[i]=='N' || d[i]=='S') ud[d[i]=='N'][x[i]].erase(y[i]);
            if(d[i]=='E' || d[i]=='W') lr[d[i]=='E'][y[i]].erase(x[i]);
            if(d[i]=='S' || d[i]=='E') d1[d[i]=='S'][x[i]+y[i]].erase(x[i]);
            if(d[i]=='N' || d[i]=='W') d2[d[i]=='N'][x[i]+y[i]].erase(x[i]);
            if(d[i]=='S' || d[i]=='W') d3[d[i]=='S'][x[i]-y[i]].erase(x[i]);
            if(d[i]=='N' || d[i]=='E') d4[d[i]=='N'][x[i]-y[i]].erase(x[i]);
        }
        unordered_map<int, bool> chk2;
        auto f=[&](int x) {
            if(!chk[x] && !chk2[x]) chk2[x]=true, st.erase({md[x], x}), md[x]=minDist(x), st.insert({md[x], x});
        };
        for(int i:vec) {
            if(d[i]=='N') {
                auto p=ud[1][x[i]].lower_bound(y[i]);
                if(p!=ud[1][x[i]].begin()) p=prev(p), f(udc[{x[i], *p}]);
                p=d2[1][x[i]+y[i]].lower_bound(x[i]);
                if(p!=d2[1][x[i]+y[i]].begin()) p=prev(p), f(d2c[{x[i]+y[i], *p}]);
                p=d4[1][x[i]-y[i]].lower_bound(x[i]);
                if(p!=d4[1][x[i]-y[i]].end()) f(d4c[{x[i]-y[i], *p}]);
            }
            else if(d[i]=='S') {
                auto p=ud[0][x[i]].lower_bound(y[i]);
                if(p!=ud[0][x[i]].end()) f(udc[{x[i], *p}]);
                p=d1[1][x[i]+y[i]].lower_bound(x[i]);
                if(p!=d1[1][x[i]+y[i]].end()) f(d1c[{x[i]+y[i], *p}]);
                p=d3[1][x[i]-y[i]].lower_bound(x[i]);
                if(p!=d3[1][x[i]-y[i]].begin()) p=prev(p), f(d3c[{x[i]-y[i], *p}]);
            }
            else if(d[i]=='E') {
                auto p=lr[1][y[i]].lower_bound(x[i]);
                if(p!=lr[1][y[i]].begin()) p=prev(p), f(lrc[{y[i], *p}]);
                p=d1[0][x[i]+y[i]].lower_bound(x[i]);
                if(p!=d1[0][x[i]+y[i]].begin()) p=prev(p), f(d1c[{x[i]+y[i], *p}]);
                p=d4[0][x[i]-y[i]].lower_bound(x[i]);
                if(p!=d4[0][x[i]-y[i]].begin()) p=prev(p), f(d4c[{x[i]-y[i], *p}]);
            }
            else {
                auto p=lr[0][y[i]].lower_bound(x[i]);
                if(p!=lr[0][y[i]].end()) f(lrc[{y[i], *p}]);
                p=d2[0][x[i]+y[i]].lower_bound(x[i]);
                if(p!=d2[0][x[i]+y[i]].end()) f(d2c[{x[i]+y[i], *p}]);
                p=d3[0][x[i]-y[i]].lower_bound(x[i]);
                if(p!=d3[0][x[i]-y[i]].end()) f(d3c[{x[i]-y[i], *p}]);
            }
        }
    }
    for(int i:ans) cout<<i<<"\n";
    return 0;
}

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