oj.uz

Submission #574010

# Submission time Handle Problem Language Result Execution time Memory
574010 2022-06-07T14:58:16 Z PedroBigMan Sky Walking (IOI19_walk) C++14
0 / 100
 4000 ms 18444 KB 
/*
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); 
	multiset<pl> active; //{height,min_dist} 
	active.insert({0LL,0LL});
	multiset<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())
		{
			//if(active.lower_bound({en[i][j],0LL})==active.end()) {continue;}
			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")
      |

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3664 KB Output is correct
2 Correct 81 ms 5152 KB Output is correct
3 Correct 96 ms 6300 KB Output is correct
4 Correct 125 ms 13360 KB Output is correct
5 Correct 161 ms 18444 KB Output is correct
6 Correct 146 ms 15676 KB Output is correct
7 Correct 67 ms 10628 KB Output is correct
8 Correct 90 ms 15084 KB Output is correct
9 Correct 152 ms 17140 KB Output is correct
10 Correct 85 ms 16432 KB Output is correct
11 Execution timed out 4083 ms 4524 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3664 KB Output is correct
2 Correct 81 ms 5152 KB Output is correct
3 Correct 96 ms 6300 KB Output is correct
4 Correct 125 ms 13360 KB Output is correct
5 Correct 161 ms 18444 KB Output is correct
6 Correct 146 ms 15676 KB Output is correct
7 Correct 67 ms 10628 KB Output is correct
8 Correct 90 ms 15084 KB Output is correct
9 Correct 152 ms 17140 KB Output is correct
10 Correct 85 ms 16432 KB Output is correct
11 Execution timed out 4083 ms 4524 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -