Fence Obstacle Course

C++14(g++5.4) 解法, 执行用时: 38ms, 内存消耗: 9080K, 提交时间: 2020-08-07 23:14:50

#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <stack>
#include <bitset>
#include <complex>

#define INF 0x3f3f3f3f
#define IMAX 2147483646;
#define LINF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define cp complex<double>

using namespace::std;

const int maxn = 211111;
struct T {
	int l, r;
	int val, add;
}t[maxn * 4];

void update(int p) {
	t[p].val = max(t[p * 2].val, t[p * 2 + 1].val);
}

void change(int p) {
	if (t[p].add == 0) return;
	t[p * 2].val = t[p * 2].add = t[p].add;
	t[p * 2 + 1].val = t[p * 2 + 1].add = t[p].add;
	t[p].add = 0;
}

void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r;
	if (l == r) { t[p].val = 0; return; }
	int mid = (l + r) / 2;
	build(p * 2, l, mid);
	build(p * 2 + 1, mid + 1, r);
	update(p);
}

void change(int p, int l, int r, int val) {
	if (t[p].l >= l && t[p].r <= r) {
		t[p].add = val;
		t[p].val = val;
		return;
	}
	change(p);
	int mid = (t[p].l + t[p].r) / 2;
	if (mid >= l) change(p * 2, l, r, val);
	if (mid + 1 <= r) change(p * 2 + 1, l, r, val);
	update(p);
}

int ask(int p, int l, int r) {
	if (t[p].l >= l && t[p].r <= r) return t[p].val;
	change(p);
	int ans = 0;
	int mid = (t[p].l + t[p].r) / 2;
	if (mid >= l)ans = max(ans,ask(p * 2, l, r));
	if (mid < r)ans = max(ans, ask(p * 2 + 1, l, r));
	return ans;
}

int n, s, a[maxn][2], f[maxn][2];
const int l = 200001, p = 100001;

signed main() {
	scanf("%d%d", &n, &s);
	build(1, 1, l);
	f[0][0] = f[0][1] = 0;
	a[0][0] = a[0][1] = 0;
	for (int i = 1,t; i <= n; i++) {
		scanf("%d%d", &a[i][0], &a[i][1]);
		t = ask(1, a[i][0] + p, a[i][0] + p);
		f[i][0] = min(f[t][0] + abs(a[i][0] - a[t][0]),
			f[t][1] + abs(a[i][0] - a[t][1]));

		t = ask(1, a[i][1] + p, a[i][1] + p);
		f[i][1] = min(f[t][0] + abs(a[i][1] - a[t][0]),
			f[t][1] + abs(a[i][1] - a[t][1]));

		change(1, a[i][0] + p, a[i][1] + p, i);
	}
	printf("%d\n", min(f[n][0] + abs(s - a[n][0]),
		f[n][1] + abs(s - a[n][1])));
	
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 32ms, 内存消耗: 5584K, 提交时间: 2020-03-02 18:43:13

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<math.h>
#include<stdio.h>
using namespace std;
const int INF=1e9;
const int maxn=1e5;
int n,s;
int a[maxn*2+5];
int b[maxn*2+5];
int dp[maxn*2+5][2];
int cover[maxn*8+5];
void pushdown(int node)
{
	if(cover[node]!=0)
	{
		cover[node<<1]=cover[node];
		cover[node<<1|1]=cover[node];
		cover[node]=0;
	}
}
void update(int node,int l,int r,int L,int R,int tag)
{
	if(L<=l&&r<=R)
	{
		cover[node]=tag;
		return;
	}
	pushdown(node);
	int mid=(l+r)>>1;
	if(L<=mid) update(node<<1,l,mid,L,R,tag);
	if(R>mid) update(node<<1|1,mid+1,r,L,R,tag);
}
int query(int node,int l,int r,int tag)
{
	if(l==r)
	{
		return cover[node];
	}
	pushdown(node);
	int mid=(l+r)>>1;
	if(tag<=mid) return query(node<<1,l,mid,tag);
	else return query(node<<1|1,mid+1,r,tag);
}
int main()
{
	scanf("%d%d",&n,&s);
	s+=maxn;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		a[i]+=maxn;
		b[i]+=maxn;
	}
	memset(cover,0,sizeof(cover));
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++)
	{
		int x=query(1,1,maxn*2,a[i]);
		int y=query(1,1,maxn*2,b[i]);
		if(x==0) dp[i][0]=abs(a[i]-maxn);
		else dp[i][0]=min(dp[x][0]+abs(a[i]-a[x]),dp[x][1]+abs(a[i]-b[x]));
		if(y==0) dp[i][1]=abs(b[i]-maxn);
		else dp[i][1]=min(dp[y][0]+abs(b[i]-a[y]),dp[y][1]+abs(b[i]-b[y]));
		update(1,1,maxn*2,a[i],b[i],i);
	}
	printf("%d\n",min(dp[n][0]+abs(s-a[n]),dp[n][1]+abs(s-b[n])));
	return 0;
}

详情