답안 #98025 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98025	2019-02-19T21:55:12 Z	Alexa2001	Golf (JOI17_golf)	C++17	100 / 100	5781 ms	318744 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[Nmax*4];

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)
    {
        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	65 ms	94328 KB	Output is correct
2	Correct	62 ms	94336 KB	Output is correct
3	Correct	66 ms	94328 KB	Output is correct
4	Correct	85 ms	94432 KB	Output is correct
5	Correct	78 ms	95584 KB	Output is correct
6	Correct	82 ms	95608 KB	Output is correct
7	Correct	98 ms	95480 KB	Output is correct
8	Correct	87 ms	95612 KB	Output is correct
9	Correct	83 ms	95612 KB	Output is correct
10	Correct	83 ms	95652 KB	Output is correct
11	Correct	79 ms	95608 KB	Output is correct
12	Correct	71 ms	95584 KB	Output is correct
13	Correct	73 ms	95480 KB	Output is correct
14	Correct	85 ms	95512 KB	Output is correct
15	Correct	71 ms	94968 KB	Output is correct
16	Correct	68 ms	95864 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	65 ms	94328 KB	Output is correct
2	Correct	62 ms	94336 KB	Output is correct
3	Correct	66 ms	94328 KB	Output is correct
4	Correct	85 ms	94432 KB	Output is correct
5	Correct	78 ms	95584 KB	Output is correct
6	Correct	82 ms	95608 KB	Output is correct
7	Correct	98 ms	95480 KB	Output is correct
8	Correct	87 ms	95612 KB	Output is correct
9	Correct	83 ms	95612 KB	Output is correct
10	Correct	83 ms	95652 KB	Output is correct
11	Correct	79 ms	95608 KB	Output is correct
12	Correct	71 ms	95584 KB	Output is correct
13	Correct	73 ms	95480 KB	Output is correct
14	Correct	85 ms	95512 KB	Output is correct
15	Correct	71 ms	94968 KB	Output is correct
16	Correct	68 ms	95864 KB	Output is correct
17	Correct	69 ms	95864 KB	Output is correct
18	Correct	93 ms	95868 KB	Output is correct
19	Correct	78 ms	95788 KB	Output is correct
20	Correct	70 ms	95864 KB	Output is correct
21	Correct	90 ms	95864 KB	Output is correct
22	Correct	79 ms	95864 KB	Output is correct
23	Correct	87 ms	95864 KB	Output is correct
24	Correct	80 ms	95864 KB	Output is correct
25	Correct	74 ms	95864 KB	Output is correct
26	Correct	81 ms	95992 KB	Output is correct
27	Correct	78 ms	95096 KB	Output is correct
28	Correct	79 ms	95992 KB	Output is correct
29	Correct	70 ms	96040 KB	Output is correct

Subtask #3
70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	65 ms	94328 KB	Output is correct
2	Correct	62 ms	94336 KB	Output is correct
3	Correct	66 ms	94328 KB	Output is correct
4	Correct	85 ms	94432 KB	Output is correct
5	Correct	78 ms	95584 KB	Output is correct
6	Correct	82 ms	95608 KB	Output is correct
7	Correct	98 ms	95480 KB	Output is correct
8	Correct	87 ms	95612 KB	Output is correct
9	Correct	83 ms	95612 KB	Output is correct
10	Correct	83 ms	95652 KB	Output is correct
11	Correct	79 ms	95608 KB	Output is correct
12	Correct	71 ms	95584 KB	Output is correct
13	Correct	73 ms	95480 KB	Output is correct
14	Correct	85 ms	95512 KB	Output is correct
15	Correct	71 ms	94968 KB	Output is correct
16	Correct	68 ms	95864 KB	Output is correct
17	Correct	69 ms	95864 KB	Output is correct
18	Correct	93 ms	95868 KB	Output is correct
19	Correct	78 ms	95788 KB	Output is correct
20	Correct	70 ms	95864 KB	Output is correct
21	Correct	90 ms	95864 KB	Output is correct
22	Correct	79 ms	95864 KB	Output is correct
23	Correct	87 ms	95864 KB	Output is correct
24	Correct	80 ms	95864 KB	Output is correct
25	Correct	74 ms	95864 KB	Output is correct
26	Correct	81 ms	95992 KB	Output is correct
27	Correct	78 ms	95096 KB	Output is correct
28	Correct	79 ms	95992 KB	Output is correct
29	Correct	70 ms	96040 KB	Output is correct
30	Correct	4612 ms	312800 KB	Output is correct
31	Correct	4692 ms	313304 KB	Output is correct
32	Correct	5171 ms	312200 KB	Output is correct
33	Correct	4884 ms	314032 KB	Output is correct
34	Correct	5068 ms	318744 KB	Output is correct
35	Correct	5285 ms	317380 KB	Output is correct
36	Correct	5015 ms	316024 KB	Output is correct
37	Correct	5046 ms	313892 KB	Output is correct
38	Correct	5781 ms	317724 KB	Output is correct
39	Correct	5115 ms	313964 KB	Output is correct
40	Correct	1164 ms	148240 KB	Output is correct
41	Correct	1122 ms	147784 KB	Output is correct
42	Correct	1115 ms	148424 KB	Output is correct
43	Correct	1104 ms	147168 KB	Output is correct
44	Correct	1216 ms	148276 KB	Output is correct
45	Correct	1218 ms	148964 KB	Output is correct
46	Correct	1329 ms	149344 KB	Output is correct
47	Correct	1117 ms	147560 KB	Output is correct
48	Correct	1202 ms	148840 KB	Output is correct
49	Correct	1198 ms	150680 KB	Output is correct
50	Correct	80 ms	95992 KB	Output is correct
51	Correct	77 ms	95992 KB	Output is correct
52	Correct	70 ms	95968 KB	Output is correct

답안 #98025

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