Submission #634578

#	Time	Username	Problem	Language	Result	Execution time	Memory
634578		qwerasdfzxcl	Sky Walking (IOI19_walk)	C++17	33 / 100	648 ms	95720 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll INF = 4e18;
struct Seg{
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> tree[200200];
    int sz;
    void init(int n){sz = n;}
    void update(int x, ll val, int e){
        x += sz;
        for (;x;x>>=1) tree[x].emplace(val, e);
    }
    ll query(int l, int r, int s){
        ++r;
        ll ret = INF;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1){
                while(!tree[l].empty() && tree[l].top().second < s) tree[l].pop();
                if (!tree[l].empty()) ret = min(ret, tree[l].top().first);
                l++;
            }
            if (r&1){
                --r;
                while(!tree[r].empty() && tree[r].top().second < s) tree[r].pop();
                if (!tree[r].empty()) ret = min(ret, tree[r].top().first);
            }
        }
        return ret;
    }
}tree1, tree2;

struct Line{
    int l, r, y, i;
    Line(){}
    Line(int _l, int _r, int _y, int _i): l(_l), r(_r), y(_y), i(_i) {}
    bool operator < (const Line &L) const{
        return tie(l, y) < tie(L.l, L.y);
    }
}E[100100];
ll D[100100];

ll myabs(ll x){return x<0?-x:x;}
ll dist(ll x1, ll y1, ll x2, ll y2){return myabs(x1-x2) + myabs(y1-y2);}

vector<int> cy;
int getidx(int y){return lower_bound(cy.begin(), cy.end(), y) - cy.begin();}

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	int n = x.size(), m = l.size();
	if (n==1) return 0;
	for (int i=0;i<m;i++) E[i] = Line(x[l[i]], x[r[i]], y[i], i);
	sort(E, E+m);

	cy = y;
	cy.push_back(0);
	sort(cy.begin(), cy.end());
	cy.erase(unique(cy.begin(), cy.end()), cy.end());
	tree1.init(m+1);
	tree2.init(m+1);

	tree1.update(0, dist(x[0], 0, 1e9, 1e9), x[0]);
	fill(D, D+m, INF);
	//printf("ok\n");

    for (int i=0;i<m;){
        int j = i;
        for (;j<m;j++) if (E[i].l!=E[j].l) break;

        for (int k=i;k<j;k++){
            D[k] = min(D[k], tree1.query(0, getidx(E[k].y), E[k].l) - dist(E[k].l, E[k].y, 1e9, 1e9));
        }
        for (int k=j-1;k>=i;k--){
            D[k] = min(D[k], tree2.query(getidx(E[k].y)+1, m, E[k].l) - dist(E[k].l, E[k].y, 1e9, 0));
        }

        for (int k=i;k<j;k++){
            tree1.update(getidx(E[k].y), D[k] + dist(E[k].l, E[k].y, 1e9, 1e9), E[k].r);
            tree2.update(getidx(E[k].y), D[k] + dist(E[k].l, E[k].y, 1e9, 0), E[k].r);
        }

        i = j;
    }

    //for (int i=0;i<m;i++) printf(" %d %d %d -> %lld\n", E[i].l, E[i].r, E[i].y, D[i]);

    ll ans = INF;
    for (int i=0;i<m;i++) if (E[i].r==x[g]) ans = min(ans, D[i] + dist(E[i].l, E[i].y, x[g], 0));
    return ans>=INF/2?-1:ans;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 0 / 43