Submission #98026

#	Time	Username	Problem	Language	Result	Execution time	Memory
98026		Alexa2001	Golf (JOI17_golf)	C++17	100 / 100	5526 ms	318708 KiB

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[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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70