Submission #1208600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208600		byunjaewoo	Naval battle (CEOI24_battle)	C++20	46 / 100	3102 ms	209464 KiB

Main

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

const int N=200010, INF=1e9+1e8;
int n, x[N], y[N], md[3][N];
int xx[N], yy[N], pl[N], ms[N];
char d[N];
bool chk[N];
vector<int> cx, cy, cp, cm;
set<int> ud[2][N], lr[2][N], d1[2][N], d2[2][N], d3[2][N], d4[2][N];
map<pair<int, int>, int> udc, lrc, d1c, d2c, d3c, d4c;
set<int> ans;
set<pair<int, int>> st;

int minDist(int k, int t) {
    int ret=INF;
    if(d[k]=='N') {
        if(!t || t==1) {
            md[0][k]=INF;
            auto p=ud[0][xx[k]].lower_bound(y[k]);
            if(p!=ud[0][xx[k]].begin()) {
                p=prev(p);
                auto q=ud[1][xx[k]].lower_bound(y[k]);
                if(q==ud[1][xx[k]].begin() || (*prev(q))<(*p)) md[0][k]=min(md[0][k], (y[k]-(*p))/2);
            }
        }
        if(!t || t==2) {
            md[1][k]=INF;
            auto p=d2[0][pl[k]].lower_bound(x[k]);
            if(p!=d2[0][pl[k]].end()) {
                auto q=d2[1][pl[k]].upper_bound(x[k]);
                if(q==d2[1][pl[k]].end() || (*q)>(*p)) md[1][k]=min(md[1][k], (*p)-x[k]);
            }
        }
        if(!t || t==3) {
            md[2][k]=INF;
            auto p=d4[0][ms[k]].lower_bound(x[k]);
            if(p!=d4[0][ms[k]].begin()) {
                p=prev(p);
                auto q=d4[1][ms[k]].lower_bound(x[k]);
                if(q==d4[1][ms[k]].begin() || (*prev(q))<(*p)) md[2][k]=min(md[2][k], x[k]-(*p));
            }
        }
    }
    else if(d[k]=='S') {
        if(!t || t==4) {
            md[0][k]=INF;
            auto p=ud[1][xx[k]].lower_bound(y[k]);
            if(p!=ud[1][xx[k]].end()) {
                auto q=next(ud[0][xx[k]].lower_bound(y[k]));
                if(q==ud[0][xx[k]].end() || (*q)>(*p)) md[0][k]=min(md[0][k], ((*p)-y[k])/2);
            }
        }
        if(!t || t==5) {
            md[1][k]=INF;
            auto p=d1[0][pl[k]].lower_bound(x[k]);
            if(p!=d1[0][pl[k]].begin()) {
                p=prev(p);
                auto q=d1[1][pl[k]].lower_bound(x[k]);
                if(q==d1[1][pl[k]].begin() || (*prev(q))<(*p)) md[1][k]=min(md[1][k], x[k]-(*p));
            }
        }
        if(!t || t==6) {
            md[2][k]=INF;
            auto p=d3[0][ms[k]].lower_bound(x[k]);
            if(p!=d3[0][ms[k]].end()) {
                auto q=next(d3[1][ms[k]].lower_bound(x[k]));
                if(q==d3[1][ms[k]].end() || (*q)>(*p)) md[2][k]=min(md[2][k], (*p)-x[k]);
            }
        }
    }
    else if(d[k]=='E') {
        if(!t || t==7) {
            md[0][k]=INF;
            auto p=lr[0][yy[k]].lower_bound(x[k]);
            if(p!=lr[0][yy[k]].end()) {
                auto q=next(lr[1][yy[k]].lower_bound(x[k]));
                if(q==lr[1][yy[k]].end() || (*q)>(*p)) md[0][k]=min(md[0][k], ((*p)-x[k])/2);
            }
        }
        if(!t || t==8) {
            md[1][k]=INF;
            auto p=d1[1][pl[k]].lower_bound(x[k]);
            if(p!=d1[1][pl[k]].end()) {
                auto q=next(d1[0][pl[k]].lower_bound(x[k]));
                if(q==d1[0][pl[k]].end() || (*q)>(*p)) md[1][k]=min(md[1][k], (*p)-x[k]);
            }
        }
        if(!t || t==9) {
            md[2][k]=INF;
            auto p=d4[1][ms[k]].lower_bound(x[k]);
            if(p!=d4[1][ms[k]].end()) {
                auto q=next(d4[0][ms[k]].lower_bound(x[k]));
                if(q==d4[0][ms[k]].end() || (*q)>(*p)) md[2][k]=min(md[2][k], (*p)-x[k]);
            }
        }
    }
    else if(d[k]=='W') {
        if(!t || t==10) {
            md[0][k]=INF;
            auto p=lr[1][yy[k]].lower_bound(x[k]);
            if(p!=lr[1][yy[k]].begin()) {
                p=prev(p);
                auto q=lr[0][yy[k]].lower_bound(x[k]);
                if(q==lr[0][yy[k]].begin() || (*prev(q))<(*p)) md[0][k]=min(md[0][k], (x[k]-(*p))/2);
            }
        }
        if(!t || t==11) {
            md[1][k]=INF;
            auto p=d2[1][pl[k]].lower_bound(x[k]);
            if(p!=d2[1][pl[k]].begin()) {
                p=prev(p);
                auto q=d2[0][pl[k]].lower_bound(x[k]);
                if(q==d2[0][pl[k]].begin() || (*prev(q))<(*p)) md[1][k]=min(md[1][k], x[k]-(*p));
            }
        }
        if(!t || t==12) {
            md[2][k]=INF;
            auto p=d3[1][ms[k]].lower_bound(x[k]);
            if(p!=d3[1][ms[k]].begin()) {
                p=prev(p);
                auto q=d3[0][ms[k]].lower_bound(x[k]);
                if(q==d3[0][ms[k]].begin() || (*prev(q))<(*p)) md[2][k]=min(md[2][k], x[k]-(*p));
            }
        }
    }
    return min({md[0][k], md[1][k], md[2][k]});
}

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];
        cx.push_back(x[i]), cy.push_back(y[i]), cp.push_back(x[i]+y[i]), cm.push_back(x[i]-y[i]);
    }
    sort(cx.begin(), cx.end()), cx.erase(unique(cx.begin(), cx.end()), cx.end());
    sort(cy.begin(), cy.end()), cy.erase(unique(cy.begin(), cy.end()), cy.end());
    sort(cp.begin(), cp.end()), cp.erase(unique(cp.begin(), cp.end()), cp.end());
    sort(cm.begin(), cm.end()), cm.erase(unique(cm.begin(), cm.end()), cm.end());
    for(int i=1; i<=n; i++) {
        xx[i]=lower_bound(cx.begin(), cx.end(), x[i])-cx.begin()+1;
        yy[i]=lower_bound(cy.begin(), cy.end(), y[i])-cy.begin()+1;
        pl[i]=lower_bound(cp.begin(), cp.end(), x[i]+y[i])-cp.begin()+1;
        ms[i]=lower_bound(cm.begin(), cm.end(), x[i]-y[i])-cm.begin()+1;
        if(d[i]=='N' || d[i]=='S') ud[d[i]=='N'][xx[i]].insert(y[i]), udc[{x[i], y[i]}]=i;
        if(d[i]=='E' || d[i]=='W') lr[d[i]=='E'][yy[i]].insert(x[i]), lrc[{y[i], x[i]}]=i;
        if(d[i]=='S' || d[i]=='E') d1[d[i]=='S'][pl[i]].insert(x[i]), d1c[{x[i]+y[i], x[i]}]=i;
        if(d[i]=='N' || d[i]=='W') d2[d[i]=='N'][pl[i]].insert(x[i]), d2c[{x[i]+y[i], x[i]}]=i;
        if(d[i]=='S' || d[i]=='W') d3[d[i]=='S'][ms[i]].insert(x[i]), d3c[{x[i]-y[i], x[i]}]=i;
        if(d[i]=='N' || d[i]=='E') d4[d[i]=='N'][ms[i]].insert(x[i]), d4c[{x[i]-y[i], x[i]}]=i;
    }
    for(int i=1; i<=n; i++) st.insert({minDist(i, 0), 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'][xx[i]].erase(y[i]);
            if(d[i]=='E' || d[i]=='W') lr[d[i]=='E'][yy[i]].erase(x[i]);
            if(d[i]=='S' || d[i]=='E') d1[d[i]=='S'][pl[i]].erase(x[i]);
            if(d[i]=='N' || d[i]=='W') d2[d[i]=='N'][pl[i]].erase(x[i]);
            if(d[i]=='S' || d[i]=='W') d3[d[i]=='S'][ms[i]].erase(x[i]);
            if(d[i]=='N' || d[i]=='E') d4[d[i]=='N'][ms[i]].erase(x[i]);
        }
        auto f=[&](int x, int t=0) {
            if(!chk[x]) st.erase({min({md[0][x], md[1][x], md[2][x]}), x}), st.insert({minDist(x, t), x});
        };
        for(int i:vec) {
            if(d[i]=='N') {
                auto p=ud[1][xx[i]].lower_bound(y[i]);
                if(p!=ud[1][xx[i]].end()) f(udc[{x[i], *p}], 1);
                p=d2[1][pl[i]].lower_bound(x[i]);
                if(p!=d2[1][pl[i]].begin()) p=prev(p), f(d2c[{x[i]+y[i], *p}], 2);
                p=d4[1][ms[i]].lower_bound(x[i]);
                if(p!=d4[1][ms[i]].end()) f(d4c[{x[i]-y[i], *p}], 3);

                p=ud[0][xx[i]].lower_bound(y[i]);
                if(p!=ud[0][xx[i]].begin()) p=prev(p), f(udc[{x[i], *p}], 4);
                p=d2[0][pl[i]].lower_bound(x[i]);
                if(p!=d2[0][pl[i]].end()) f(d2c[{x[i]+y[i], *p}], 11);
                p=d4[0][ms[i]].lower_bound(x[i]);
                if(p!=d4[0][ms[i]].begin()) p=prev(p), f(d4c[{x[i]-y[i], *p}], 9);
            }
            else if(d[i]=='S') {
                auto p=ud[0][xx[i]].lower_bound(y[i]);
                if(p!=ud[0][xx[i]].begin()) p=prev(p), f(udc[{x[i], *p}], 4);
                p=d1[1][pl[i]].lower_bound(x[i]);
                if(p!=d1[1][pl[i]].end()) f(d1c[{x[i]+y[i], *p}], 5);
                p=d3[1][ms[i]].lower_bound(x[i]);
                if(p!=d3[1][ms[i]].begin()) p=prev(p), f(d3c[{x[i]-y[i], *p}], 6);

                p=ud[1][xx[i]].lower_bound(y[i]);
                if(p!=ud[1][xx[i]].end()) f(udc[{x[i], *p}], 1);
                p=d1[0][pl[i]].lower_bound(x[i]);
                if(p!=d1[0][pl[i]].begin()) p=prev(p), f(d1c[{x[i]+y[i], *p}], 8);
                p=d3[0][ms[i]].lower_bound(x[i]);
                if(p!=d3[0][ms[i]].end()) f(d3c[{x[i]-y[i], *p}], 12);
            }
            else if(d[i]=='E') {
                auto p=lr[1][yy[i]].lower_bound(x[i]);
                if(p!=lr[1][yy[i]].begin()) p=prev(p), f(lrc[{y[i], *p}], 7);
                p=d1[0][pl[i]].lower_bound(x[i]);
                if(p!=d1[0][pl[i]].begin()) p=prev(p), f(d1c[{x[i]+y[i], *p}], 8);
                p=d4[0][ms[i]].lower_bound(x[i]);
                if(p!=d4[0][ms[i]].begin()) p=prev(p), f(d4c[{x[i]-y[i], *p}], 9);

                p=lr[0][yy[i]].lower_bound(x[i]);
                if(p!=lr[0][yy[i]].end()) f(lrc[{y[i], *p}], 10);
                p=d1[1][pl[i]].lower_bound(x[i]);
                if(p!=d1[1][pl[i]].end()) f(d1c[{x[i]+y[i], *p}], 5);
                p=d4[1][ms[i]].lower_bound(x[i]);
                if(p!=d4[1][ms[i]].end()) f(d4c[{x[i]-y[i], *p}], 3);
            }
            else {
                auto p=lr[0][yy[i]].lower_bound(x[i]);
                if(p!=lr[0][yy[i]].end()) f(lrc[{y[i], *p}], 10);
                p=d2[0][pl[i]].lower_bound(x[i]);
                if(p!=d2[0][pl[i]].end()) f(d2c[{x[i]+y[i], *p}], 11);
                p=d3[0][ms[i]].lower_bound(x[i]);
                if(p!=d3[0][ms[i]].end()) f(d3c[{x[i]-y[i], *p}], 12);

                p=lr[1][yy[i]].lower_bound(x[i]);
                if(p!=lr[1][yy[i]].begin()) p=prev(p), f(lrc[{y[i], *p}], 7);
                p=d2[1][pl[i]].lower_bound(x[i]);
                if(p!=d2[1][pl[i]].begin()) p=prev(p), f(d2c[{x[i]+y[i], *p}], 2);
                p=d3[1][ms[i]].lower_bound(x[i]);
                if(p!=d3[1][ms[i]].begin()) p=prev(p), f(d3c[{x[i]-y[i], *p}], 6);
            }
        }
    }
    for(int i:ans) cout<<i<<"\n";
    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: 0 / 30
• Subtask 7: 0 / 24