oj.uz

Submission #573974

# Submission time Handle Problem Language Result Execution time Memory
573974 2022-06-07T14:06:04 Z PedroBigMan Sky Walking (IOI19_walk) C++14
15 / 100
 177 ms 18468 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) 
{
	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 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 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 26 ms 3676 KB Output is correct
2 Correct 86 ms 5152 KB Output is correct
3 Correct 95 ms 6296 KB Output is correct
4 Correct 139 ms 13416 KB Output is correct
5 Correct 162 ms 18396 KB Output is correct
6 Correct 155 ms 15684 KB Output is correct
7 Correct 67 ms 10564 KB Output is correct
8 Correct 98 ms 15176 KB Output is correct
9 Correct 177 ms 17140 KB Output is correct
10 Correct 91 ms 16432 KB Output is correct
11 Correct 12 ms 4552 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3676 KB Output is correct
2 Correct 86 ms 5152 KB Output is correct
3 Correct 95 ms 6296 KB Output is correct
4 Correct 139 ms 13416 KB Output is correct
5 Correct 162 ms 18396 KB Output is correct
6 Correct 155 ms 15684 KB Output is correct
7 Correct 67 ms 10564 KB Output is correct
8 Correct 98 ms 15176 KB Output is correct
9 Correct 177 ms 17140 KB Output is correct
10 Correct 91 ms 16432 KB Output is correct
11 Correct 12 ms 4552 KB Output is correct
12 Correct 94 ms 6308 KB Output is correct
13 Correct 85 ms 12996 KB Output is correct
14 Correct 163 ms 18468 KB Output is correct
15 Correct 109 ms 13512 KB Output is correct
16 Correct 109 ms 13508 KB Output is correct
17 Correct 119 ms 13512 KB Output is correct
18 Correct 115 ms 13504 KB Output is correct
19 Correct 109 ms 13508 KB Output is correct
20 Correct 75 ms 10624 KB Output is correct
21 Correct 26 ms 8756 KB Output is correct
22 Incorrect 62 ms 11576 KB Output isn't correct
23 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 -