oj.uz

Submission #573970

# Submission time Handle Problem Language Result Execution time Memory
573970 2022-06-07T14:00:04 Z PedroBigMan Sky Walking (IOI19_walk) C++14
15 / 100
 168 ms 18600 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 10000000000000000LL
#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) 
{
	set<ll> em; set<ll>::iterator it3 = em.lower_bound(0); if(it3!=em.end()) {DEBUG(0);}
 	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});
	set<pl>::iterator under,over; ll d_under,d_over;
	ll he,L; vector<pl> newval;
	REP(i,0,N)
	{
		if(active.size()==0) {break;}
		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}));
			if(active.size()==0) {break;}
		}
		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 1 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 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3656 KB Output is correct
2 Correct 86 ms 5076 KB Output is correct
3 Correct 99 ms 6292 KB Output is correct
4 Correct 155 ms 13444 KB Output is correct
5 Correct 160 ms 18600 KB Output is correct
6 Correct 149 ms 15792 KB Output is correct
7 Correct 68 ms 10656 KB Output is correct
8 Correct 90 ms 15172 KB Output is correct
9 Correct 168 ms 17028 KB Output is correct
10 Correct 91 ms 16428 KB Output is correct
11 Correct 11 ms 4528 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3656 KB Output is correct
2 Correct 86 ms 5076 KB Output is correct
3 Correct 99 ms 6292 KB Output is correct
4 Correct 155 ms 13444 KB Output is correct
5 Correct 160 ms 18600 KB Output is correct
6 Correct 149 ms 15792 KB Output is correct
7 Correct 68 ms 10656 KB Output is correct
8 Correct 90 ms 15172 KB Output is correct
9 Correct 168 ms 17028 KB Output is correct
10 Correct 91 ms 16428 KB Output is correct
11 Correct 11 ms 4528 KB Output is correct
12 Correct 91 ms 6296 KB Output is correct
13 Correct 74 ms 13044 KB Output is correct
14 Correct 159 ms 18480 KB Output is correct
15 Correct 111 ms 13516 KB Output is correct
16 Correct 117 ms 13532 KB Output is correct
17 Correct 118 ms 13504 KB Output is correct
18 Correct 113 ms 13504 KB Output is correct
19 Correct 112 ms 13468 KB Output is correct
20 Correct 74 ms 10596 KB Output is correct
21 Correct 26 ms 8748 KB Output is correct
22 Incorrect 63 ms 11564 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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