제출 #1154580

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154580		Pacybwoah	Sky Walking (IOI19_walk)	C++20	15 / 100	197 ms	28600 KiB

walk

#include "walk.h"
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<set>
typedef long long ll;
const ll inf = 1e16;
using namespace std;
struct BIT{
    vector<ll> bit;
    int n;
    BIT(int _n){
        n = _n;
        bit.resize(n + 1);
		fill(bit.begin(), bit.end(), inf);
    }
    void modify(int pos, ll val){
        while(pos <= n){
            bit[pos] = min(bit[pos], val);
            pos += (pos & -pos);
        }
    }
    int query(int pos){
     	ll ans = inf;
        while(pos > 0){
            ans = min(ans, bit[pos]);
            pos -= (pos & -pos);
        }
        return ans;
    }
};
struct st{
	vector<ll> seg;
	st(int n){
		seg.resize(4 * n + 4);
		fill(seg.begin(), seg.end(), inf);
	}
	void modify(int l, int r, int pos, ll num, int ind){
		if(l == r){
			seg[ind] = num;
			return;
		}
		int mid = (l + r) >> 1;
		if(pos <= mid) modify(l, mid, pos, num, ind * 2);
		else modify(mid + 1, r, pos, num, ind * 2 + 1);
		seg[ind] = min(seg[ind * 2], seg[ind * 2 + 1]);
	}
	ll query(int l, int r, int start, int end, int ind){
		if(r < start || end < l) return inf;
		if(start <= l && r <= end) return seg[ind];
		int mid = (l + r) >> 1;
		return min(query(l, mid, start, end, ind * 2), query(mid + 1, r, start, end, ind * 2 + 1));
	}
};
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) {
	vector<ll> cp;
	int n = (int)x.size(), m = (int)l.size();
	for(int i = 0; i < n; i++) cp.push_back(h[i]);
	for(int i = 0; i < m; i++) cp.push_back(y[i]);
	cp.push_back(0);
	sort(cp.begin(), cp.end());
	cp.resize(unique(cp.begin(), cp.end()) - cp.begin());
	for(auto &xx: h){
		xx = lower_bound(cp.begin(), cp.end(), xx) - cp.begin() + 1;
	}
	for(auto &xx: y){
		xx = lower_bound(cp.begin(), cp.end(), xx) - cp.begin() + 1;
	}
	vector<vector<int>> in(n), out(n);
	vector<ll> lst(m);
	for(int i = 0; i < m; i++){
		in[l[i]].push_back(i);
		out[r[i]].push_back(i);
	}
	int sz = (int)cp.size();
	if(s == 0 && g == n - 1){
		// cp[pos - 1]
		st cis(sz);
		st trans(sz);
		cis.modify(1, sz, 1, 0, 1);
		trans.modify(1, sz, 1, 0, 1);
		cp.insert(cp.begin(), 0);
		for(int i = 0; i < n; i++){
			vector<ll> dps((int)in[i].size());
			int cnt = 0;
			for(auto &id: in[i]){
				ll dp = inf;
				dp = min(dp, cis.query(1, sz, 1, y[id], 1) + cp[y[id]]);
				if(h[i] > y[id]) dp = min(dp, trans.query(1, sz, y[id], h[i], 1) - cp[y[id]]);
				dps[cnt] = dp;
				cnt++;
			}
			if(i < n - 1) for(auto &id: out[i]){
				cis.modify(1, sz, y[id], inf, 1);
				trans.modify(1, sz, y[id], inf, 1);
			}
			if(i == 0){
				cis.modify(1, sz, 1, inf, 1);
				trans.modify(1, sz, 1, inf, 1);
			}
			cnt = 0;
			for(auto &id: in[i]){
				cis.modify(1, sz, y[id], dps[cnt] - cp[y[id]], 1);
				trans.modify(1, sz, y[id], dps[cnt] + cp[y[id]], 1);
				cnt++;
			}
		}
		ll ans = inf;
		for(int i = 1; i <= h[n - 1]; i++){
			ans = min(ans, cis.query(1, sz, i, i, 1) + cp[i] + cp[i]);
			ans = min(ans, trans.query(1, sz, i, i, 1));
			//cout << i << " " << cis.query(1, sz, i, i, 1) + cp[i] << " " << trans.query(1, sz, i, i, 1) - cp[i] << "\n";
		}
		if(ans == inf) return -1;
		return ans + x[n - 1] - x[0];
	}

	return 1;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp walk.cpp

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