답안 #98024 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98024	2019-02-19T21:54:12 Z	Alexa2001	Golf (JOI17_golf)	C++17	30 / 100	3198 ms	631672 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];

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	64 ms	94332 KB	Output is correct
2	Correct	64 ms	94328 KB	Output is correct
3	Correct	74 ms	94248 KB	Output is correct
4	Correct	60 ms	94432 KB	Output is correct
5	Correct	73 ms	95564 KB	Output is correct
6	Correct	79 ms	95480 KB	Output is correct
7	Correct	80 ms	95608 KB	Output is correct
8	Correct	74 ms	95484 KB	Output is correct
9	Correct	72 ms	95480 KB	Output is correct
10	Correct	87 ms	95608 KB	Output is correct
11	Correct	73 ms	95636 KB	Output is correct
12	Correct	75 ms	95608 KB	Output is correct
13	Correct	68 ms	95480 KB	Output is correct
14	Correct	72 ms	95608 KB	Output is correct
15	Correct	73 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	64 ms	94332 KB	Output is correct
2	Correct	64 ms	94328 KB	Output is correct
3	Correct	74 ms	94248 KB	Output is correct
4	Correct	60 ms	94432 KB	Output is correct
5	Correct	73 ms	95564 KB	Output is correct
6	Correct	79 ms	95480 KB	Output is correct
7	Correct	80 ms	95608 KB	Output is correct
8	Correct	74 ms	95484 KB	Output is correct
9	Correct	72 ms	95480 KB	Output is correct
10	Correct	87 ms	95608 KB	Output is correct
11	Correct	73 ms	95636 KB	Output is correct
12	Correct	75 ms	95608 KB	Output is correct
13	Correct	68 ms	95480 KB	Output is correct
14	Correct	72 ms	95608 KB	Output is correct
15	Correct	73 ms	94968 KB	Output is correct
16	Correct	68 ms	95864 KB	Output is correct
17	Correct	89 ms	96008 KB	Output is correct
18	Correct	81 ms	95840 KB	Output is correct
19	Correct	73 ms	95864 KB	Output is correct
20	Correct	78 ms	95888 KB	Output is correct
21	Correct	99 ms	95840 KB	Output is correct
22	Correct	90 ms	95864 KB	Output is correct
23	Correct	87 ms	95840 KB	Output is correct
24	Correct	101 ms	95864 KB	Output is correct
25	Correct	78 ms	95828 KB	Output is correct
26	Correct	76 ms	95872 KB	Output is correct
27	Correct	74 ms	95096 KB	Output is correct
28	Correct	74 ms	95992 KB	Output is correct
29	Correct	80 ms	95992 KB	Output is correct

Subtask #3
0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	64 ms	94332 KB	Output is correct
2	Correct	64 ms	94328 KB	Output is correct
3	Correct	74 ms	94248 KB	Output is correct
4	Correct	60 ms	94432 KB	Output is correct
5	Correct	73 ms	95564 KB	Output is correct
6	Correct	79 ms	95480 KB	Output is correct
7	Correct	80 ms	95608 KB	Output is correct
8	Correct	74 ms	95484 KB	Output is correct
9	Correct	72 ms	95480 KB	Output is correct
10	Correct	87 ms	95608 KB	Output is correct
11	Correct	73 ms	95636 KB	Output is correct
12	Correct	75 ms	95608 KB	Output is correct
13	Correct	68 ms	95480 KB	Output is correct
14	Correct	72 ms	95608 KB	Output is correct
15	Correct	73 ms	94968 KB	Output is correct
16	Correct	68 ms	95864 KB	Output is correct
17	Correct	89 ms	96008 KB	Output is correct
18	Correct	81 ms	95840 KB	Output is correct
19	Correct	73 ms	95864 KB	Output is correct
20	Correct	78 ms	95888 KB	Output is correct
21	Correct	99 ms	95840 KB	Output is correct
22	Correct	90 ms	95864 KB	Output is correct
23	Correct	87 ms	95840 KB	Output is correct
24	Correct	101 ms	95864 KB	Output is correct
25	Correct	78 ms	95828 KB	Output is correct
26	Correct	76 ms	95872 KB	Output is correct
27	Correct	74 ms	95096 KB	Output is correct
28	Correct	74 ms	95992 KB	Output is correct
29	Correct	80 ms	95992 KB	Output is correct
30	Runtime error	3198 ms	631672 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Halted	0 ms	0 KB	-

답안 #98024

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 70.0

Subtask #1
10.0 / 10.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 70.0