Submission #1312645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312645		Zbyszek99	Golf (JOI17_golf)	C++20	30 / 100	1883 ms	995416 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[18000000];
bool odw[18000000];
int left_node[18000000];
int right_node[18000000];
vector<segx> x_segs;
vector<segy> y_segs;

int build(int l, int r)
{
    int ind = cur_vert;
    cur_vert+=2;
    if(l==r) return ind;
    left_node[ind] = build(l,(l+r)/2);
    right_node[ind] = build((l+r)/2+1,r);
    graph[left_node[ind]+1].pb({ind+1,0});
    graph[right_node[ind]+1].pb({ind+1,0});
    return ind;
}
int change_vert(int p, int v, int prev, int l, int r)
{
    int ind = cur_vert;
    cur_vert += 2;
    if(l == r)
    {
        if(v != -1)
        {
            graph[ind].pb({v,0});
            graph[v].pb({ind+1,1});
        }
        return ind;
    }
    if(p <= (l+r)/2)
    {
        right_node[ind] = right_node[prev];
        left_node[ind] = change_vert(p,v,left_node[prev],l,(l+r)/2);
    }
    else
    {
        left_node[ind] = left_node[prev];
        right_node[ind] = change_vert(p,v,right_node[prev],(l+r)/2+1,r);   
    }
    graph[left_node[ind]+1].pb({ind+1,0});
    graph[right_node[ind]+1].pb({ind+1,0});  
    return ind;  
}
void con_seg(int l2, int r2, int v, int l, int r, int vert)
{
    if(r < l2 || l > r2) return;
    if(l >= l2 && r <= r2)
    {
        graph[v].pb({vert,1});
        graph[vert+1].pb({v,0});
        return;
    }
    con_seg(l2,r2,v,l,(l+r)/2,left_node[vert]);
    con_seg(l2,r2,v,(l+r)/2+1,r,right_node[vert]);
}

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(t.ff % 2 == 0)
            {
                if(left_node[t.ff] != 0)
                {
                    q.push_front({left_node[t.ff],t.ss});
                    q.push_front({right_node[t.ff],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);
    if(cur_vert%2 == 1) cur_vert++;
    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;
    int tree_ = build(0,(1<<19)-1);
    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)
            {
                int new_tree = change_vert(x_segs[v].y,v,tree_,0,(1<<19)-1);
                tree_ = new_tree;
            }
            else
            {
                int new_tree = change_vert(x_segs[v].y,-1,tree_,0,(1<<19)-1);
                tree_ = new_tree;
            }
            cur_event++;
        }
        con_seg(it.y1,it.y2,cur_y,0,(1<<19)-1,tree_);
        cur_y++;
    }
    cout << bfs(x1,y1,x2,y2) << "\n";
}

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