Submission #932371

#	Time	Username	Problem	Language	Result	Execution time	Memory
932371		beepbeepsheep	Sky Walking (IOI19_walk)	C++17	33 / 100	304 ms	68404 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define iiii tuple<ll,ll,ll,ll>
const ll maxn=1e5+5;
const ll inf=1e15;
struct node{
	ll s,e,m,val;
	node *l,*r;
	node(ll _s, ll _e){
		s=_s,e=_e,m=(s+e)>>1,val=inf;
		if (s!=e) l=new node(s,m),r=new node(m+1,e);
	}
	void upd(ll x, ll v){
		if (s==e){
			val=v;
			return;
		}
		if (x>m) r->upd(x,v);
		else l->upd(x,v);
		val=min(l->val,r->val);
	}
	ll query(ll x, ll y){
		if (x<=s && e<=y) return val;
		if (x>m) return r->query(x,y);
		if (y<=m) return l->query(x,y);
		return min(l->query(x,y),r->query(x,y));
	}
}*small, *big;
vector<iiii> bridges;
bool cmp(iiii a, iiii b){
	if (get<2>(a)==get<2>(b)) return get<0>(a)>get<0>(b);
	return get<2>(a)<get<2>(b);
}

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) {
	ll n=x.size(),m=l.size();
	assert(s==0 && g==n-1);
	small=new node(1,n);
	big=new node(1,n);
	for (int i=0;i<m;i++) bridges.emplace_back(l[i],r[i],y[i],i);
	sort(bridges.begin(),bridges.end(),cmp); //sorted by height
	vector<iiii> queries; //time, off/on, where to toggle, original height
	for (int i=0;i<m;i++){
		ll a,b,c,d;
		tie(a,b,c,d)=bridges[i];
		queries.emplace_back(a,0,i+1,c);
		queries.emplace_back(b,1,i+1,c);
	}
	queries.emplace_back(0,1,0,0);
	sort(queries.begin(),queries.end());
	ll ptr=0;
	small=new node(0,m+5),big=new node(0,m+5);
	small->upd(0,0);
	for (int i=0;i<n-1;i++){
		while (ptr!=queries.size() && get<0>(queries[ptr])<=i){
			ll a,b,c,d;
			tie(a,d,b,c)=queries[ptr];
			if (d==0){
				ll lo=small->query(0,b-1)+c;
				ll hi=big->query(b+1,m+5)-c;
				ll res=min(lo,hi);
				small->upd(b,res-c); //get dominated
				big->upd(b,res+c); //dominated
			} else{
				small->upd(b,inf);
				big->upd(b,inf); //reset to sentinels
			}
			ptr++;
		}
	}
	ll ans=big->query(0,m+5); //0 is under everything
	if (ans==inf) return -1;
	return ans+x.back()-x.front();
}

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:57:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   while (ptr!=queries.size() && get<0>(queries[ptr])<=i){
      |          ~~~^~~~~~~~~~~~~~~~

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