Submission #1312639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312639		Zbyszek99	Golf (JOI17_golf)	C++20	30 / 100	2208 ms	1114112 KiB

golf

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

struct rect
{
    int x1,x2,y1,y2;
};

struct segx
{
    int x1,x2,y;
    bool operator<(const segx& other) const
    {
        if(x1 != other.x1) return x1<other.x1;
        if(x2 != other.x2) return x2<other.x2;
        return y<other.y;
    }
};

struct segy
{
    int y1,y2,x;
    bool operator<(const segy& other)
    {
        return x<other.x;
    }
};

struct node;

int cur_vert = 0;
vector<pair<int,bool>> graph[15000000];
bool odw[15000000];
node* my_node[15000000];
vector<segx> x_segs;
vector<segy> y_segs;

struct node
{
    int l = 0;
    int r = (1<<19)-1;
    node* left = NULL;
    node* right = NULL;
    int vert_ind = 0;
    void build()
    {
        vert_ind = cur_vert;
        my_node[cur_vert] = this;
        my_node[cur_vert+1] = this;
        cur_vert+=2;
        if(l==r) return;
        left = new node;
        left -> l = l;
        left -> r = (l+r)/2;
        right = new node;
        right -> l = (l+r)/2+1;
        right -> r = r;
        left->build();
        right->build();
        graph[left->vert_ind+1].pb({vert_ind+1,0});
        graph[right->vert_ind+1].pb({vert_ind+1,0});
    }
    void change_vert(int p, int v, node* prev)
    {
        vert_ind = cur_vert;
        my_node[cur_vert] = this;
        my_node[cur_vert+1] = this;
        cur_vert += 2;
        if(l == r)
        {
            if(v != -1)
            {
                graph[vert_ind].pb({v,0});
                graph[v].pb({vert_ind+1,1});
            }
            return;
        }
        if(p <= (l+r)/2)
        {
            right = prev->right;
            left = new node;
            left -> l = l;
            left -> r = (l+r)/2;
            left -> change_vert(p,v,prev->left);
        }
        else
        {
            left = prev->left;
            right = new node;
            right -> l = (l+r)/2+1;
            right -> r = r;
            right -> change_vert(p,v,prev->right);   
        }
        graph[left->vert_ind+1].pb({vert_ind+1,0});
        graph[right->vert_ind+1].pb({vert_ind+1,0});    
    }
    void con_seg(int l2, int r2, int v)
    {
        if(r < l2 || l > r2) return;
        if(l >= l2 && r <= r2)
        {
            graph[v].pb({vert_ind,1});
            graph[vert_ind+1].pb({v,0});
            return;
        }
        left->con_seg(l2,r2,v);
        right->con_seg(l2,r2,v);
    }
};

int bfs(int x1, int y1, int x2, int y2)
{
    rep(i,cur_vert) odw[i] = 0;
    deque<pii> q;
    rep(i,siz(x_segs)) if(x_segs[i].x1 <= x1 && x_segs[i].x2 >= x1 && x_segs[i].y == y1) q.push_front({i,0});
    rep(i,siz(y_segs)) if(y_segs[i].y1 <= y1 && y_segs[i].y2 >= y1 && y_segs[i].x == x1) q.push_front({i+siz(x_segs),0});
    int ans = 1e9;
    while(!q.empty())
    {
        pii t = q.front();
        q.pop_front();
        if(odw[t.ff]) continue;
        odw[t.ff] = 1;
        if(t.ff < siz(x_segs) && x_segs[t.ff].x1 <= x2 && x_segs[t.ff].x2 >= x2 && x_segs[t.ff].y == y2)
        {
            ans = t.ss+1;
            break;
        }
        if(t.ff >= siz(x_segs) && t.ff < siz(x_segs)+siz(y_segs) && y_segs[t.ff-siz(x_segs)].y1 <= y2 && y_segs[t.ff-siz(x_segs)].y2 >= y2 && y_segs[t.ff-siz(x_segs)].x == x2)
        {
            ans = t.ss+1;
            break;
        }
        forall(it,graph[t.ff]) if(it.ss == 0) q.push_front({it.ff,t.ss}); else q.push_back({it.ff,t.ss+1});
        if(t.ff >= siz(x_segs)+siz(y_segs)) 
        {
            if(my_node[t.ff]->vert_ind == t.ff)
            {
                if(my_node[t.ff]->l != my_node[t.ff]->r)
                {
                    q.push_front({my_node[t.ff]->left->vert_ind,t.ss});
                    q.push_front({my_node[t.ff]->right->vert_ind,t.ss});
                }
            }
        }
    }
    return ans;
}

int main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int n;
    cin >> n;
    vector<rect> rects(n);
    rep(i,n) cin >> rects[i].x1 >> rects[i].x2 >> rects[i].y1 >> rects[i].y2;
    map<int,int> mx;
    map<int,int> my;
    mx[x1] = 1;
    mx[x2] = 1;
    my[y1] = 1;
    my[y2] = 1;
    forall(it,rects) 
    {
        mx[it.x1] = 1;
        mx[it.x2] = 1;
        my[it.y1] = 1;
        my[it.y2] = 1;
    }
    int cur = 1;
    forall(it,mx) mx[it.ff] = cur++;
    cur = 1;
    forall(it,my) my[it.ff] = cur++;
    x1 = mx[x1];
    x2 = mx[x2];
    y1 = my[y1];
    y2 = my[y2];
    forall(it,rects)
    {
        it.x1 = mx[it.x1];
        it.x2 = mx[it.x2];
        it.y1 = my[it.y1];
        it.y2 = my[it.y2];
    }
    vector<pii> seg_points;
    seg_points.pb({x1,y1});
    seg_points.pb({x2,y2});
    forall(it,rects)
    {
        seg_points.pb({it.x1,it.y1});
        seg_points.pb({it.x2,it.y2});
    }
    vector<pair<int,pii>> bor;
    // calc_y
    forall(it,rects) 
    {
        if(it.x2-it.x1 <= 1) continue;
        bor.pb({it.x1+1,{it.y1,1}});
        bor.pb({it.x2,{it.y1,-1}});
        bor.pb({it.x1+1,{it.y2,1}});
        bor.pb({it.x2,{it.y2,-1}});
    }
    sort(all(bor));
    sort(all(seg_points));
    set<int> bor_set;
    int cur_bor = 0;
    forall(it,seg_points)
    {
        while(cur_bor < siz(bor) && bor[cur_bor].ff <= it.ff)
        {
            if(bor[cur_bor].ss.ss == 1) bor_set.insert(bor[cur_bor].ss.ff);
            else bor_set.erase(bor[cur_bor].ss.ff);
            cur_bor++;
        }
        int prv = 0;
        int nxt = siz(my)+2;
        auto nxt_ptr = bor_set.lower_bound(it.ss);
        if(nxt_ptr != bor_set.end()) nxt = *nxt_ptr;
        if(nxt_ptr != bor_set.begin()) prv = *(--nxt_ptr);
        y_segs.pb({prv,nxt,it.ff});
    }
    // calc_x
    bor = {};
    forall(it,rects) 
    {
        if(it.y2-it.y1 <= 1) continue;
        bor.pb({it.y1+1,{it.x1,1}});
        bor.pb({it.y2,{it.x1,-1}});
        bor.pb({it.y1+1,{it.x2,1}});
        bor.pb({it.y2,{it.x2,-1}});
    }
    sort(all(bor));
    forall(it,seg_points) swap(it.ff,it.ss);
    sort(all(seg_points));
    forall(it,seg_points) swap(it.ff,it.ss);
    bor_set = {};
    cur_bor = 0;
    forall(it,seg_points)
    {
        while(cur_bor < siz(bor) && bor[cur_bor].ff <= it.ss)
        {
            if(bor[cur_bor].ss.ss == 1) bor_set.insert(bor[cur_bor].ss.ff);
            else bor_set.erase(bor[cur_bor].ss.ff);
            cur_bor++;
        }
        int prv = 0;
        int nxt = siz(mx)+2;
        auto nxt_ptr = bor_set.lower_bound(it.ff);
        if(nxt_ptr != bor_set.end()) nxt = *nxt_ptr;
        if(nxt_ptr != bor_set.begin()) prv = *(--nxt_ptr);
        x_segs.pb({prv,nxt,it.ss});
    }
    set<segx> pom;
    forall(it,x_segs) pom.insert(it);
    x_segs = {};
    forall(it,pom) x_segs.pb(it);
    cur_vert = siz(x_segs)+siz(y_segs);
    vector<pair<int,pii>> events;
    rep(i,siz(x_segs))
    {
        events.pb({x_segs[i].x1,{i,1}});
        events.pb({x_segs[i].x2+1,{i,-1}});
    }
    sort(all(events));
    sort(all(y_segs));
    int cur_event = 0;
    node tree_;
    tree_.build();
    int cur_y = siz(x_segs);
    forall(it,y_segs)
    {
        while(cur_event < siz(events) && events[cur_event].ff <= it.x)
        {
            int v = events[cur_event].ss.ff;
            if(events[cur_event].ss.ss == 1)
            {
                node new_tree;
                new_tree.change_vert(x_segs[v].y,v,&tree_);
                tree_ = new_tree;
            }
            else
            {
                node new_tree;
                new_tree.change_vert(x_segs[v].y,-1,&tree_);
                tree_ = new_tree;
            }
            cur_event++;
        }
        tree_.con_seg(it.y1,it.y2,cur_y);
        cur_y++;
    }
    cout << bfs(x1,y1,x2,y2) << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70