답안 #98026 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98026	2019-02-19T22:04:09 Z	Alexa2001	Golf (JOI17_golf)	C++17	100 / 100	5526 ms	318708 KB

golf

#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)

using namespace std;

const int Nmax = 2e5 + 5;


int X1, X2, Y1, Y2, n, limx, limy, StartV, StartH, FinishV, FinishH, ids;
int D[4*Nmax];

vector<int> allx, ally, start[Nmax], finish[Nmax];
vector< pair<int,int> > V[Nmax], H[Nmax];
vector<int> vec;

struct point
{
    int x, y;
} S, F;

struct Node
{
    int p, l, r, id;
};
vector<Node> segmV, segmH;


class SegmentTree
{
    int a[Nmax<<2];
public:
    int N;
    void update(int node, int st, int dr, int pos, int add)
    {
        if(st == dr)
        {
            a[node] += add;
            return;
        }
        if(pos <= mid) update(left_son, st, mid, pos, add);
            else update(right_son, mid+1, dr, pos, add);
        a[node] = a[left_son] + a[right_son];
    }

    int before(int node, int st, int dr, int pos)
    {
        if(!a[node]) return 1;
        if(st == dr) return st;

        if(dr <= pos)
        {
            int ans = before(right_son, mid+1, dr, pos);
            if(ans == 1) ans = before(left_son, st, mid, pos);
            return ans;
        }
        else
        {
            int ans = 1;
            if(mid+1 <= pos) ans = before(right_son, mid+1, dr, pos);
            if(ans == 1) ans = before(left_son, st, mid, pos);
            return ans;
        }
    }

    int after(int node, int st, int dr, int pos)
    {
        if(!a[node]) return N;
        if(st == dr) return st;

        if(st >= pos)
        {
            int ans = after(left_son, st, mid, pos);
            if(ans == N) ans = after(right_son, mid+1, dr, pos);
            return ans;
        }
        else
        {
            int ans = N;
            if(pos <= mid) ans = after(left_son, st, mid, pos);
            if(ans == N) ans = after(right_son, mid+1, dr, pos);
            return ans;
        }
    }
} aint;



void read()
{
    int i, X1, X2, Y1, Y2;
    cin >> S.x >> S.y >> F.x >> F.y;
    cin >> n;
    for(i=0; i<n; ++i)
    {
        cin >> X1 >> X2 >> Y1 >> Y2;
        allx.push_back(X1); allx.push_back(X2);
        ally.push_back(Y1); ally.push_back(Y2);
    }
}

void normalize()
{
    map<int,int> mpx, mpy;
    int X1, Y1, X2, Y2, i;

    allx.push_back(S.x); allx.push_back(F.x);
    ally.push_back(S.y); ally.push_back(F.y);
    for(auto it : allx) mpx[it] = 1;
    for(auto it : ally) mpy[it] = 1;

    for(auto &it : mpx) it.second = ++limx;
    for(auto &it : mpy) it.second = ++limy;

    S.x = mpx[S.x]; S.y = mpy[S.y]; F.x = mpx[F.x]; F.y = mpy[F.y];

    for(i=0; i<n; ++i)
    {
        X1 = mpx[allx[2*i]];
        X2 = mpx[allx[2*i+1]];
        Y1 = mpy[ally[2*i]];
        Y2 = mpy[ally[2*i+1]];

        V[X1].push_back({Y1, Y2});
        V[X2].push_back({Y1, Y2});
        H[Y1].push_back({X1, X2});
        H[Y2].push_back({X1, X2});
    }
    V[S.x].push_back({S.y, S.y});
    V[F.x].push_back({F.y, F.y});
    H[S.y].push_back({S.x, S.x});
    H[F.y].push_back({F.x, F.x});
}

void expand_vertically()
{
    //aint.clear();
    int i;
    for(i=1; i<=limx; ++i) start[i].clear(), finish[i].clear();

    for(i=1; i<=limy; ++i)
        for(auto it : H[i])
            if(it.first != it.second)
            {
                start[it.first].push_back(i);
                finish[it.second].push_back(i);
            }
    aint.N = limy;
    for(i=1; i<=limx; ++i)
    {
        for(auto it : finish[i]) aint.update(1, 1, limy, it, -1);

        for(auto it : V[i])
        {
            int x, y;
            x = aint.before(1, 1, limy, it.first);
            y = aint.after(1, 1, limy, it.second);
            segmV.push_back({i, x, y, ++ids});

            if(it.first == it.second)
            {
                if(S.x == i && S.y == it.first) StartV = ids;
                    else if(F.x == i && F.y == it.first) FinishV = ids;
            }
        }

        for(auto it : start[i]) aint.update(1, 1, limy, it, 1);
    }
}
void expand_horizontally()
{
  //  aint.clear();
    int i;
    for(i=1; i<=limy; ++i) start[i].clear(), finish[i].clear();

    for(i=1; i<=limx; ++i)
        for(auto it : V[i])
            if(it.first != it.second)
            {
                start[it.first].push_back(i);
                finish[it.second].push_back(i);
            }

    aint.N = limx;
    for(i=1; i<=limy; ++i)
    {
        for(auto it : finish[i]) aint.update(1, 1, limx, it, -1);

        for(auto it : H[i])
        {
            int x, y;
            x = aint.before(1, 1, limx, it.first);
            y = aint.after(1, 1, limx, it.second);
            segmH.push_back({i, x, y, ++ids});

            if(it.first == it.second)
            {
                if(S.x == it.first && S.y == i) StartH = ids;
                    else if(F.x == it.first && F.y == i) FinishH = ids;
            }
        }

        for(auto it : start[i]) aint.update(1, 1, limx, it, 1);
    }
}


class Kawaii
{
    set< pair<int,int> > s[Nmax<<2];
public:
    void update(int node, int st, int dr, int L, int R, int pos, int id)
    {
        if(L <= st && dr <= R)
        {
            s[node].insert({pos, id});
            return;
        }
        if(L <= mid) update(left_son, st, mid, L, R, pos, id);
        if(mid < R) update(right_son, mid+1, dr, L, R, pos, id);
    }

    void take(int node, int l, int r)
    {
        if(s[node].empty()) return;
        set< pair<int,int> > :: iterator it, itt;
        it = itt = s[node].lower_bound({l, 0});

        while(it != s[node].end() && it->first <= r)
        {
            if(D[it->second] == -1) vec.push_back(it->second);
            ++it;
        }
        s[node].erase(itt, it);
    }

    void query(int node, int st, int dr, int L, int R, int P)
    {
        take(node, L, R);
        if(st == dr) return;

        if(P <= mid) query(left_son, st, mid, L, R, P);
            else query(right_son, mid+1, dr, L, R, P);
    }

} hor, ver;


void create_tree()
{
    for(auto it : segmV)
        ver.update(1, 1, limy, it.l, it.r, it.p, it.id);
    for(auto it : segmH)
        hor.update(1, 1, limx, it.l, it.r, it.p, it.id);
}

void vecini(int node)
{
    vec.clear();
    if(node <= 2*n + 2) /// vertical
    {
        Node act = segmV[node-1];
        hor.query(1, 1, limx, act.l, act.r, act.p);
    }
    else
    {
        Node act = segmH[node-1-(2*n+2)];
        ver.query(1, 1, limy, act.l, act.r, act.p);
    }
}

void bfs()
{
    int node, i;
    queue<int> q;

    for(i=1; i<=ids; ++i) D[i] = -1;

    D[StartV] = D[StartH] = 0;
    q.push(StartV); q.push(StartH);

    while(q.size())
    {
        node = q.front();
        q.pop();

        vecini(node);

        for(auto it : vec)
        {
            D[it] = D[node] + 1;
            q.push(it);
        }
    }

    int ans = 1e9;

    for(auto it : segmV)
        if(F.x == it.p && it.l<=F.y && F.y<=it.r)
            ans = min(ans, D[it.id] + 1);
    for(auto it : segmH)
        if(F.y == it.p && it.l<=F.x && F.x<=it.r)
            ans = min(ans, D[it.id]+1);
    cout << ans << '\n';
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    read();
    normalize();
    expand_vertically();
    expand_horizontally();
    create_tree();
    bfs();

    return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	94456 KB	Output is correct
2	Correct	96 ms	94328 KB	Output is correct
3	Correct	114 ms	94304 KB	Output is correct
4	Correct	69 ms	94456 KB	Output is correct
5	Correct	71 ms	95480 KB	Output is correct
6	Correct	80 ms	95480 KB	Output is correct
7	Correct	80 ms	95484 KB	Output is correct
8	Correct	105 ms	95480 KB	Output is correct
9	Correct	86 ms	95608 KB	Output is correct
10	Correct	70 ms	95608 KB	Output is correct
11	Correct	70 ms	95484 KB	Output is correct
12	Correct	72 ms	95612 KB	Output is correct
13	Correct	76 ms	95480 KB	Output is correct
14	Correct	72 ms	95608 KB	Output is correct
15	Correct	63 ms	94968 KB	Output is correct
16	Correct	82 ms	95864 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	94456 KB	Output is correct
2	Correct	96 ms	94328 KB	Output is correct
3	Correct	114 ms	94304 KB	Output is correct
4	Correct	69 ms	94456 KB	Output is correct
5	Correct	71 ms	95480 KB	Output is correct
6	Correct	80 ms	95480 KB	Output is correct
7	Correct	80 ms	95484 KB	Output is correct
8	Correct	105 ms	95480 KB	Output is correct
9	Correct	86 ms	95608 KB	Output is correct
10	Correct	70 ms	95608 KB	Output is correct
11	Correct	70 ms	95484 KB	Output is correct
12	Correct	72 ms	95612 KB	Output is correct
13	Correct	76 ms	95480 KB	Output is correct
14	Correct	72 ms	95608 KB	Output is correct
15	Correct	63 ms	94968 KB	Output is correct
16	Correct	82 ms	95864 KB	Output is correct
17	Correct	72 ms	95992 KB	Output is correct
18	Correct	75 ms	95880 KB	Output is correct
19	Correct	82 ms	95864 KB	Output is correct
20	Correct	84 ms	95864 KB	Output is correct
21	Correct	85 ms	95864 KB	Output is correct
22	Correct	73 ms	95864 KB	Output is correct
23	Correct	76 ms	95864 KB	Output is correct
24	Correct	84 ms	95864 KB	Output is correct
25	Correct	87 ms	95864 KB	Output is correct
26	Correct	83 ms	95864 KB	Output is correct
27	Correct	81 ms	95100 KB	Output is correct
28	Correct	99 ms	96044 KB	Output is correct
29	Correct	88 ms	95996 KB	Output is correct

Subtask #3
70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	94456 KB	Output is correct
2	Correct	96 ms	94328 KB	Output is correct
3	Correct	114 ms	94304 KB	Output is correct
4	Correct	69 ms	94456 KB	Output is correct
5	Correct	71 ms	95480 KB	Output is correct
6	Correct	80 ms	95480 KB	Output is correct
7	Correct	80 ms	95484 KB	Output is correct
8	Correct	105 ms	95480 KB	Output is correct
9	Correct	86 ms	95608 KB	Output is correct
10	Correct	70 ms	95608 KB	Output is correct
11	Correct	70 ms	95484 KB	Output is correct
12	Correct	72 ms	95612 KB	Output is correct
13	Correct	76 ms	95480 KB	Output is correct
14	Correct	72 ms	95608 KB	Output is correct
15	Correct	63 ms	94968 KB	Output is correct
16	Correct	82 ms	95864 KB	Output is correct
17	Correct	72 ms	95992 KB	Output is correct
18	Correct	75 ms	95880 KB	Output is correct
19	Correct	82 ms	95864 KB	Output is correct
20	Correct	84 ms	95864 KB	Output is correct
21	Correct	85 ms	95864 KB	Output is correct
22	Correct	73 ms	95864 KB	Output is correct
23	Correct	76 ms	95864 KB	Output is correct
24	Correct	84 ms	95864 KB	Output is correct
25	Correct	87 ms	95864 KB	Output is correct
26	Correct	83 ms	95864 KB	Output is correct
27	Correct	81 ms	95100 KB	Output is correct
28	Correct	99 ms	96044 KB	Output is correct
29	Correct	88 ms	95996 KB	Output is correct
30	Correct	5326 ms	312808 KB	Output is correct
31	Correct	4821 ms	313384 KB	Output is correct
32	Correct	5098 ms	312316 KB	Output is correct
33	Correct	4733 ms	314048 KB	Output is correct
34	Correct	4855 ms	318708 KB	Output is correct
35	Correct	4976 ms	317364 KB	Output is correct
36	Correct	5458 ms	316144 KB	Output is correct
37	Correct	5526 ms	313624 KB	Output is correct
38	Correct	4936 ms	317632 KB	Output is correct
39	Correct	4711 ms	314068 KB	Output is correct
40	Correct	972 ms	148296 KB	Output is correct
41	Correct	1202 ms	147848 KB	Output is correct
42	Correct	1112 ms	148404 KB	Output is correct
43	Correct	1179 ms	147148 KB	Output is correct
44	Correct	1031 ms	148196 KB	Output is correct
45	Correct	1033 ms	148960 KB	Output is correct
46	Correct	1125 ms	149276 KB	Output is correct
47	Correct	1084 ms	147624 KB	Output is correct
48	Correct	1075 ms	148912 KB	Output is correct
49	Correct	1154 ms	150648 KB	Output is correct
50	Correct	97 ms	95992 KB	Output is correct
51	Correct	97 ms	95992 KB	Output is correct
52	Correct	93 ms	95968 KB	Output is correct

답안 #98026

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 20.0 / 20.0

Subtask #3 70.0 / 70.0

Subtask #1
10.0 / 10.0

Subtask #2
20.0 / 20.0

Subtask #3
70.0 / 70.0