提出 #558424

---

ソースコード 拡げる

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(c) (c).begin(),(c).end()

inline void fast_erase(vector<P> &vec,P p) {
    auto it=lower_bound(all(vec),p);
    //cout<<p.first<<", "<<p.second<<endl;
    //cout<<it->first<<", "<<it->second<<endl;
    vec.erase(it);
}

int n;
ll cnt(P p,map<P,char> vec, vector<P> xs,vector<P> rxs, vector<P> ys,vector<P> rys) {
    ll ret=1;
    while(1) {
        int x=p.first;
        int y=p.second;
        char c=vec[p];
        vec.erase(p);
        //if(ret==8) break;
        //printf("[debug] %d %d %c\n",x,y,c);

        if(c=='>') {
            auto it=upper_bound(all(ys),P(y,x));
            if(it==ys.end()) break;
            p.first=it->second;
            if(it->first!=p.second) break;
            p.second=it->first;
        }
        if(c=='<') {
            auto it=upper_bound(all(rys),P(y,-x));
            if(it==rys.end()) break;
            p.first=-it->second;
            if(it->first!=p.second) break;
            p.second=it->first;
        }
        if(c=='v') {
            auto it=upper_bound(all(xs),P(x,y));
            if(it==xs.end()) break;
            if(it->first!=p.first) break;
            p=*it;
        }
        if(c=='^') {
            auto it=upper_bound(all(rxs),P(x,-y));
            if(it==rxs.end()) break;
            if(it->first!=p.first) break;
            p=*it;
            p.second*=-1;
        }
        fast_erase(xs,P(x,y));
        fast_erase(ys,P(y,x));
        fast_erase(rxs,P(x,-y));
        fast_erase(rys,P(y,-x));

        ret++;
    }

    return ret;
}
map<P, char> vec;
vector<P> xs;
vector<P> ys;
vector<P> rxs;
vector<P> rys;
int main() {
    cin>>n;
    xs.reserve(n);
    ys.reserve(n);
    rxs.reserve(n);
    rys.reserve(n);
    rep(i,n) {
        int x,y;
        char c;
        cin>>x>>y>>c;
        vec[P(x,y)]=c;
        xs.push_back(P(x,y));
        ys.push_back(P(y,x));
        rxs.push_back(P(x,-y));
        rys.push_back(P(y,-x));
    }
    sort(all(xs));
    sort(all(ys));
    sort(all(rxs));
    sort(all(rys));
    ll ans=0;


    for(const auto &e:vec) {
        const auto &p=e.first;
        ans=max(ans,cnt(p,vec,xs,rxs,ys,rys));
    }
    cout<<ans<<endl;
    return 0;
}

提出情報

ジャッジ結果