oj.uz

Submission #98024

# Submission time Handle Problem Language Result Execution time Memory
98024 2019-02-19T21:54:12 Z Alexa2001 Golf (JOI17_golf) C++17
30 / 100
 3198 ms 631672 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];

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 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

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

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