oj.uz

Submission #98026

# Submission time Handle Problem Language Result Execution time Memory
98026 2019-02-19T22:04:09 Z Alexa2001 Golf (JOI17_golf) C++17
100 / 100
 5526 ms 318708 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[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

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

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

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