Submission #872376

#	Time	Username	Problem	Language	Result	Execution time	Memory
872376		azberjibiou	영역 (JOI16_ho_t4)	C++17	100 / 100	127 ms	37608 KiB

2016_ho_t4

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=1000005;
const int mxM=500004;
const int MOD=1'000'000'007;
const ll INF=8e18;
int N, K;
char A[mxN];
pii B[mxN];
map <pii, int> mp;
vector <pii> v1, v2;
vector <pii> ct[mxN];
ll ans;
void make_B(){
    for(int i=1;i<=N;i++){
        if(A[i]=='N')   B[i]=pii(B[i-1].fi, B[i-1].se+1);
        if(A[i]=='S')   B[i]=pii(B[i-1].fi, B[i-1].se-1);
        if(A[i]=='E')   B[i]=pii(B[i-1].fi+1, B[i-1].se);
        if(A[i]=='W')   B[i]=pii(B[i-1].fi-1, B[i-1].se);
    }
}
void solv_00(){
    for(int i=0;i<N;i++){
        mp[B[i]]=1;
        v2.push_back(B[i]);
        v2.emplace_back(B[i].fi-1, B[i].se);
        v2.emplace_back(B[i].fi, B[i].se-1);
        v2.emplace_back(B[i].fi-1, B[i].se-1);
    }
    sort(all(v2));
    v2.erase(unique(all(v2)), v2.end());
    for(auto [x, y] : v2){
        if(mp[pii(x, y)]==1 && mp[pii(x+1, y)]==1 && mp[pii(x, y+1)]==1 && mp[pii(x+1, y+1)]==1)    ans++;
    }
    cout << ans;
}
void swap_xy(){
    for(int i=1;i<=N;i++){
        if(A[i]=='N')   A[i]='E';
        else if(A[i]=='S')  A[i]='W';
        else if(A[i]=='E')  A[i]='N';
        else    A[i]='S';
    }
    make_B();
}
void swap_x(){
    for(int i=1;i<=N;i++){
        if(A[i]=='E')   A[i]='W';
        else if(A[i]=='W')  A[i]='E';
    }
    make_B();
}
pair<pii, int> f(int x, int y){
    int q;
    if(x>0) q=x/B[N].fi;
    else if((-x)%B[N].fi==0)    q=-((-x)/B[N].fi);
    else    q=-((-x)/B[N].fi+1);
    return pair<pii, int>(pii(x-q*B[N].fi, y-q*B[N].se), q);
}
pair<pii, int> f(pii p){
    auto [x, y]=p;
    return f(x, y);
}
int main()
{
    gibon
    cin >> N >> K;
    cin >> A+1;
    make_B();
    if(B[N]==pii(0, 0)){
        solv_00();
        return 0;
    }
    if(B[N].fi==0)  swap_xy();
    if(B[N].fi<0)   swap_x();
    for(int i=0;i<=N;i++){
        v1.push_back(f(B[i]).fi);
        v2.push_back(f(B[i]).fi);
        v2.push_back(f(pii(B[i].fi-1, B[i].se)).fi);
        v2.push_back(f(pii(B[i].fi, B[i].se-1)).fi);
        v2.push_back(f(pii(B[i].fi-1, B[i].se-1)).fi);
    }
    sort(all(v1));
    v1.erase(unique(all(v1)), v1.end());
    sort(all(v2));
    v2.erase(unique(all(v2)), v2.end());
    //printf("v1: \n");
    //for(auto [x, y] : v1)   printf("%d %d\n", x, y);
    //printf("----------------------\n");
    for(int i=0;i<=N;i++){
        pii now=f(B[i]).fi;
        int del=f(B[i]).se;
        int ix=lower_bound(all(v1), now)-v1.begin();
        ct[ix].emplace_back(del, 1);
        ct[ix].emplace_back(del+K, -1);
    }
    for(int i=0;i<v1.size();i++)    sort(all(ct[i]));
    //for(int i=0;i<v1.size();i++){
    //    printf("x, y=%d %d: ", v1[i].fi, v1[i].se);
    //    for(auto [x, y] : ct[i])    printf("(%d %d) ", x, y);
    //    printf("\n");
    //}
    //printf("----------------\n");
    for(auto [x, y] : v2){
        //printf("x=%d, y=%d\n", x, y);
        pii n[4]={f(x, y).fi, f(x+1, y).fi, f(x, y+1).fi, f(x+1, y+1).fi}, idx[4];
        int cnt[4]={};
        idx[0].se=f(x, y).se;
        idx[1].se=f(x+1, y).se;
        idx[2].se=f(x, y+1).se;
        idx[3].se=f(x+1, y+1).se;
        bool jog=true;
        for(int i=0;i<4;i++){
            int ti=lower_bound(all(v1), n[i])-v1.begin();
            if(ti==v1.size() || v1[ti]!=n[i])   jog=false;
            idx[i].fi=lower_bound(all(v1), n[i])-v1.begin();
        }
        if(!jog)    continue;
        vector <pair<pii, int>> nct;
        for(int i=0;i<4;i++){
            for(auto [pos, typ] : ct[idx[i].fi])  nct.emplace_back(pii(pos-idx[i].se, typ), i);
        }
        sort(all(nct));
        //for(int i=0;i<nct.size();i++){
        //    printf("(%d %d %d) ", nct[i].fi.fi, nct[i].fi.se, nct[i].se);
        //}
        //printf("\n");
        for(int i=0;i+1<nct.size();i++){
            auto [pos, pm]=nct[i].fi;
            int num=nct[i].se;
            cnt[num]+=pm;
            if(cnt[0]>0 && cnt[1]>0 && cnt[2]>0 && cnt[3]>0)    ans+=nct[i+1].fi.fi-nct[i].fi.fi;
        }
        //printf("ans=%lld\n", ans);
    }
    cout << ans;
}

Compilation message (stderr)

2016_ho_t4.cpp: In function 'int main()':
2016_ho_t4.cpp:77:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |     cin >> A+1;
      |            ~^~
2016_ho_t4.cpp:106:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int i=0;i<v1.size();i++)    sort(all(ct[i]));
      |                 ~^~~~~~~~~~
2016_ho_t4.cpp:124:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |             if(ti==v1.size() || v1[ti]!=n[i])   jog=false;
      |                ~~^~~~~~~~~~~
2016_ho_t4.cpp:137:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         for(int i=0;i+1<nct.size();i++){
      |                     ~~~^~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 62 / 62