Submission #594122

#	Time	Username	Problem	Language	Result	Execution time	Memory
594122		Cross_Ratio	영역 (JOI16_ho_t4)	C++14	100 / 100	268 ms	28656 KiB

2016_ho_t4

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> P;
const int INF = 1e18;
map<P,set<int>> M;
int dx, dy;
P r(int x, int y) {
    int rx = (x%dx+dx)%dx;
    int ry = y - dy * (x-rx)/dx;
    return P(rx, ry);
}
int mx[4] = {0,0,1,1};
int my[4] = {0,1,1,0};
void print(priority_queue<P,vector<P>,greater<P>> PQ) {
    while(!PQ.empty()) {
        cout << PQ.top().first << ' ' <<PQ.top().second << '\n';
        PQ.pop();
    }
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    int K;
    cin >> N >> K;
    string s;
    cin >> s;
    int i, j;
    int x = 0, y = 0;
    set<P> S;
    S.insert(P(0,0));
    for(i=0;i<N;i++) {
        if(s[i]=='E') x++;
        if(s[i]=='W') x--;
        if(s[i]=='N') y++;
        if(s[i]=='S') y--;
        S.insert(P(x,y));
    }
    int ans = 0;
    for(P k : S) {
        int x = k.first, y = k.second;
        if(S.find(P(x,y+1))!=S.end()&&S.find(P(x+1,y))!=S.end()&&S.find(P(x+1,y+1))!=S.end()) {
            ans++;
        }
    }
    if(x==0&&y==0) {
        cout << ans;
        return 0;
    }
    dx = x, dy = y;
    if(dx==0) {
        swap(dx, dy);
        for(i=0;i<N;i++) {
            if(s[i]=='E') s[i]='N';
            else if(s[i]=='N') s[i]='E';
            else if(s[i]=='W') s[i]='S';
            else if(s[i]=='S') s[i]='W';
        }
    }
    if(dx<0) {
        dx *= -1;
        for(i=0;i<N;i++) {
            if(s[i]=='E') s[i]='W';
            else if(s[i]=='W') s[i]='E';
        }
    }
    assert(dx>0);
    x = y = 0;
    M[P(0,0)].insert(0);
    for(i=0;i<N;i++) {
        if(s[i]=='E') x++;
        if(s[i]=='W') x--;
        if(s[i]=='N') y++;
        if(s[i]=='S') y--;
        int rx = (x%dx+dx)%dx;
        int ry = y - dy * (x-rx)/dx;
        M[r(x, y)].insert((x-rx)/dx);
    }
    /*cout << dx << ' ' << dy << '\n';
    cout << s << '\n';
    for(auto it = M.begin();it!=M.end();it++) {
        cout << it->first.first << ' ' << it->first.second << " :\n";
        for(int m : it->second) cout << m << ' ';
        cout << '\n';
    }*/
    S = set<P> {};
    x = y = 0;
    S.insert(r(x,y));
    S.insert(r(x,y-1));
    S.insert(r(x-1,y-1));
    S.insert(r(x-1,y));
    for(i=0;i<N;i++) {
        if(s[i]=='E') x++;
        if(s[i]=='W') x--;
        if(s[i]=='N') y++;
        if(s[i]=='S') y--;
        int rx = (x%dx+dx)%dx;
        int ry = y - dy * (x-rx) / dx;
        S.insert(r(x,y));
        S.insert(r(x,y-1));
        S.insert(r(x-1,y-1));
        S.insert(r(x-1,y));
    }
    ans = 0;
    for(P k : S) {
        int x = k.first, y = k.second;
        //cout << x << ' ' << y << " How Many?\n";
        priority_queue<P,vector<P>,greater<P>> res;
        bool isPos=true;
        for(i=0;i<4;i++) {
            priority_queue<P,vector<P>,greater<P>> Rang;
            int x2 = x + mx[i];
            int y2 = y + my[i];
            //cout << x2 << ' ' << y2 << '\n';
            int z = 0;
            if(x2==dx) {
                x2 = 0;
                y2 -= dy;
                z = -1;
            }
            if(!M.count(P(x2,y2))) {
                isPos = false;
                break;
            }
            for(int j : M[P(x2,y2)]) {
                //cout << j << ' ';
                Rang.push(P(j+z,j+K-1+z));
            }
            //cout << '\n';
            //cout << "Current Res : \n";
            //print(res);
            //cout << "Now Rang :\n";
            //print(Rang);
            priority_queue<P,vector<P>,greater<P>> Res;
            int st = INF;
            int en = -INF;
            priority_queue<P,vector<P>,greater<P>> rang;
            while(!Rang.empty()) {
                if(st==INF) {
                    st = Rang.top().first;
                    en = st;
                }
                if(Rang.top().first<=en) {
                    en = max(en, Rang.top().second);
                    Rang.pop();
                }
                else {
                    rang.push(P(st,en));
                    st = INF;
                    en = -INF;
                }
            }
            if(st != INF) rang.push(P(st,en));
            //cout << "Rang -> rang\n";
            //print(rang);
            if(!i) {
                res = rang;
                continue;
            }
            while(!res.empty()&&!rang.empty()) {
                int x1 = res.top().first, x2 = res.top().second;
                while(!rang.empty()&&rang.top().second<x1) rang.pop();
                if(rang.empty()) break;
                int y1 = rang.top().first, y2 = rang.top().second;
                if(x2<y1) {
                    res.pop();
                }
                else {
                    Res.push(P(max(x1,y1),min(x2,y2)));
                    res.pop();
                }
            }
            //cout << "Summation\n";
            //print(Res);
            res = Res;
        }
        if(!isPos) continue;
        while(!res.empty()) {
            int k1 = res.top().first, k2 = res.top().second;
            ans += k2 - k1 + 1;
            res.pop();
        }
        //cout << ans << '\n';
    }
    cout << ans;
}

Compilation message (stderr)

2016_ho_t4.cpp: In function 'int main()':
2016_ho_t4.cpp:78:13: warning: unused variable 'ry' [-Wunused-variable]
   78 |         int ry = y - dy * (x-rx)/dx;
      |             ^~
2016_ho_t4.cpp:100:13: warning: unused variable 'ry' [-Wunused-variable]
  100 |         int ry = y - dy * (x-rx) / dx;
      |             ^~
2016_ho_t4.cpp:30:12: warning: unused variable 'j' [-Wunused-variable]
   30 |     int i, j;
      |            ^

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