/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
#include "walk.h"
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
ll N = x.size(); ll M = l.size();
vector<vector<ll> > be,en; VV(be,N,{}); VV(en,N,{});
REP(i,0,M) {be[l[i]].pb(y[i]); en[r[i]].pb(y[i]);}
be[N-1].pb(0); en[0].pb(0);
set<pl> active; //{height,min_dist}
active.insert({0LL,0LL}); active.insert({-1LL,INF});
set<pl>::iterator under,over; ll d_under,d_over;
ll he,L; vector<pl> newval;
REP(i,0,N)
{
newval.clear();
REP(j,0,be[i].size())
{
he=be[i][j]; L=h[i];
under = active.lower_bound({he,0LL}); if(under==active.begin()) {d_under=INF;} else {under--; d_under=he-under->ff + under->ss;}
over = active.lower_bound({he,0LL}); if(over==active.end() || over->ff>L) {d_over=INF;} else{d_over=over->ff-he+over->ss;}
if(min<ll>(d_over,d_under)<INF) {newval.pb({he,min<ll>(d_over,d_under)});}
}
REP(j,0,en[i].size())
{
active.erase(active.lower_bound({en[i][j],0LL}));
}
REP(j,0,newval.size()) {active.insert(newval[j]);}
}
if(active.size()==0) {return -1LL;} else {return (active.begin()->ss + x[N-1]-x[0]);}
}
Compilation message
walk.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
5 | #pragma GCC optimization ("O3")
|
walk.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
6 | #pragma GCC optimization ("unroll-loops")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
3660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
3660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
