oj.uz

Submission #98025

# Submission time Handle Problem Language Result Execution time Memory
98025 2019-02-19T21:55:12 Z Alexa2001 Golf (JOI17_golf) C++17
100 / 100
 5781 ms 318744 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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